// Copyright 2015 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.

// +build ignore

#include "ninja.h"

#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <unistd.h>

#include <algorithm>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>

#include "command.h"
#include "dep.h"
#include "eval.h"
#include "file_cache.h"
#include "fileutil.h"
#include "find.h"
#include "flags.h"
#include "func.h"
#include "io.h"
#include "log.h"
#include "stats.h"
#include "string_piece.h"
#include "stringprintf.h"
#include "strutil.h"
#include "var.h"
#include "version.h"

static size_t FindCommandLineFlag(StringPiece cmd, StringPiece name) {
  const size_t found = cmd.find(name);
  if (found == string::npos || found == 0)
    return string::npos;
  return found;
}

static StringPiece FindCommandLineFlagWithArg(StringPiece cmd,
                                              StringPiece name) {
  size_t index = FindCommandLineFlag(cmd, name);
  if (index == string::npos)
    return StringPiece();

  StringPiece val = TrimLeftSpace(cmd.substr(index + name.size()));
  index = val.find(name);
  while (index != string::npos) {
    val = TrimLeftSpace(val.substr(index + name.size()));
    index = val.find(name);
  }

  index = val.find_first_of(" \t");
  return val.substr(0, index);
}

static bool StripPrefix(StringPiece p, StringPiece* s) {
  if (!HasPrefix(*s, p))
    return false;
  *s = s->substr(p.size());
  return true;
}

size_t GetGomaccPosForAndroidCompileCommand(StringPiece cmdline) {
  size_t index = cmdline.find(' ');
  if (index == string::npos)
    return string::npos;
  StringPiece cmd = cmdline.substr(0, index);
  if (HasSuffix(cmd, "ccache")) {
    index++;
    size_t pos = GetGomaccPosForAndroidCompileCommand(cmdline.substr(index));
    return pos == string::npos ? string::npos : pos + index;
  }
  if (!StripPrefix("prebuilts/", &cmd))
    return string::npos;
  if (!StripPrefix("gcc/", &cmd) && !StripPrefix("clang/", &cmd))
    return string::npos;
  if (!HasSuffix(cmd, "gcc") && !HasSuffix(cmd, "g++") &&
      !HasSuffix(cmd, "clang") && !HasSuffix(cmd, "clang++")) {
    return string::npos;
  }

  StringPiece rest = cmdline.substr(index);
  return rest.find(" -c ") != string::npos ? 0 : string::npos;
}

static bool GetDepfileFromCommandImpl(StringPiece cmd, string* out) {
  if ((FindCommandLineFlag(cmd, " -MD") == string::npos &&
       FindCommandLineFlag(cmd, " -MMD") == string::npos) ||
      FindCommandLineFlag(cmd, " -c") == string::npos) {
    return false;
  }

  StringPiece mf = FindCommandLineFlagWithArg(cmd, " -MF");
  if (!mf.empty()) {
    mf.AppendToString(out);
    return true;
  }

  StringPiece o = FindCommandLineFlagWithArg(cmd, " -o");
  if (o.empty()) {
    ERROR("Cannot find the depfile in %s", cmd.as_string().c_str());
    return false;
  }

  StripExt(o).AppendToString(out);
  *out += ".d";
  return true;
}

bool GetDepfileFromCommand(string* cmd, string* out) {
  CHECK(!cmd->empty());
  if (!GetDepfileFromCommandImpl(*cmd, out))
    return false;

  // A hack for Android - llvm-rs-cc seems not to emit a dep file.
  if (cmd->find("bin/llvm-rs-cc ") != string::npos) {
    return false;
  }

  // TODO: A hack for Makefiles generated by automake.

  // A hack for Android to get .P files instead of .d.
  string p;
  StripExt(*out).AppendToString(&p);
  p += ".P";
  if (cmd->find(p) != string::npos) {
    const string rm_f = "; rm -f " + *out;
    const size_t found = cmd->find(rm_f);
    if (found == string::npos) {
      ERROR("Cannot find removal of .d file: %s", cmd->c_str());
    }
    cmd->erase(found, rm_f.size());
    return true;
  }

  // A hack for Android. For .s files, GCC does not use C
  // preprocessor, so it ignores -MF flag.
  string as = "/";
  StripExt(Basename(*out)).AppendToString(&as);
  as += ".s";
  if (cmd->find(as) != string::npos) {
    return false;
  }

  *cmd += "&& cp ";
  *cmd += *out;
  *cmd += ' ';
  *cmd += *out;
  *cmd += ".tmp ";
  *out += ".tmp";
  return true;
}

class NinjaGenerator {
 public:
  NinjaGenerator(const char* ninja_suffix, const char* ninja_dir, Evaluator* ev,
                 double start_time)
      : ce_(ev), ev_(ev), fp_(NULL), rule_id_(0), start_time_(start_time) {
    ev_->set_avoid_io(true);
    shell_ = ev->EvalVar(kShellSym);
    if (g_flags.goma_dir)
      gomacc_ = StringPrintf("%s/gomacc ", g_flags.goma_dir);
    if (ninja_suffix) {
      ninja_suffix_ = ninja_suffix;
    }
    if (ninja_dir) {
      ninja_dir_ = ninja_dir;
    } else {
      ninja_dir_ = ".";
    }

    GetExecutablePath(&kati_binary_);
  }

  ~NinjaGenerator() {
    ev_->set_avoid_io(false);
  }

  void Generate(const vector<DepNode*>& nodes,
                bool build_all_targets,
                const string& orig_args) {
    GenerateNinja(nodes, build_all_targets, orig_args);
    GenerateShell();
    GenerateStamp(orig_args);
  }

  static string GetStampFilename(const char* ninja_dir,
                                 const char* ninja_suffix) {
    return StringPrintf("%s/.kati_stamp%s",
                        ninja_dir ? ninja_dir : ".",
                        ninja_suffix ? ninja_suffix : "");
  }

 private:
  string GenRuleName() {
    return StringPrintf("rule%d", rule_id_++);
  }

  StringPiece TranslateCommand(const char* in, string* cmd_buf) {
    const size_t orig_size = cmd_buf->size();
    bool prev_backslash = false;
    // Set space as an initial value so the leading comment will be
    // stripped out.
    char prev_char = ' ';
    char quote = 0;
    for (; *in; in++) {
      switch (*in) {
        case '#':
          if (quote == 0 && isspace(prev_char)) {
            while (in[1] && *in != '\n')
              in++;
          } else {
            *cmd_buf += *in;
          }
          break;

        case '\'':
        case '"':
        case '`':
          if (quote) {
            if (quote == *in)
              quote = 0;
          } else if (!prev_backslash) {
            quote = *in;
          }
          *cmd_buf += *in;
          break;

        case '$':
          *cmd_buf += "$$";
          break;

        case '\n':
          if (prev_backslash) {
            cmd_buf->resize(cmd_buf->size()-1);
          } else {
            *cmd_buf += ' ';
          }
          break;

        case '\\':
          *cmd_buf += '\\';
          break;

        default:
          *cmd_buf += *in;
      }

      if (*in == '\\') {
        prev_backslash = !prev_backslash;
      } else {
        prev_backslash = false;
      }

      prev_char = *in;
    }

    if (prev_backslash) {
      cmd_buf->resize(cmd_buf->size()-1);
    }

    while (true) {
      char c = (*cmd_buf)[cmd_buf->size()-1];
      if (!isspace(c) && c != ';')
        break;
      cmd_buf->resize(cmd_buf->size() - 1);
    }

    return StringPiece(cmd_buf->data() + orig_size,
                       cmd_buf->size() - orig_size);
  }

  bool GetDescriptionFromCommand(StringPiece cmd, string *out) {
    if (!HasPrefix(cmd, "echo ")) {
      return false;
    }
    cmd = cmd.substr(5, cmd.size());

    bool prev_backslash = false;
    char quote = 0;
    string out_buf;

    // Strip outer quotes, and fail if it is not a single echo command
    for (StringPiece::iterator in = cmd.begin(); in != cmd.end(); in++) {
      if (prev_backslash) {
        prev_backslash = false;
        out_buf += *in;
      } else if (*in == '\\') {
        prev_backslash = true;
        out_buf += *in;
      } else if (quote) {
        if (*in == quote) {
          quote = 0;
        } else {
          out_buf += *in;
        }
      } else {
        switch (*in) {
        case '\'':
        case '"':
        case '`':
          quote = *in;
          break;

        case '<':
        case '>':
        case '&':
        case '|':
        case ';':
          return false;

        default:
          out_buf += *in;
        }
      }
    }

    *out = out_buf;
    return true;
  }

  bool GenShellScript(const vector<Command*>& commands,
                      string* cmd_buf,
                      string* description) {
    bool got_descritpion = false;
    bool use_gomacc = false;
    bool should_ignore_error = false;
    for (const Command* c : commands) {
      if (!cmd_buf->empty()) {
        if (should_ignore_error) {
          *cmd_buf += " ; ";
        } else {
          *cmd_buf += " && ";
        }
      }
      should_ignore_error = c->ignore_error;

      const char* in = c->cmd.c_str();
      while (isspace(*in))
        in++;

      bool needs_subshell = commands.size() > 1;
      if (*in == '(') {
        needs_subshell = false;
      }

      if (needs_subshell)
        *cmd_buf += '(';

      size_t cmd_start = cmd_buf->size();
      StringPiece translated = TranslateCommand(in, cmd_buf);
      if (g_flags.detect_android_echo && !got_descritpion && !c->echo &&
          GetDescriptionFromCommand(translated, description)) {
        got_descritpion = true;
        cmd_buf->resize(cmd_start);
        translated.clear();
      }
      if (translated.empty()) {
        *cmd_buf += "true";
      } else if (g_flags.goma_dir) {
        size_t pos = GetGomaccPosForAndroidCompileCommand(translated);
        if (pos != string::npos) {
          cmd_buf->insert(cmd_start + pos, gomacc_);
          use_gomacc = true;
        }
      } else if (translated.find("/gomacc") != string::npos) {
        use_gomacc = true;
      }

      if (c == commands.back() && c->ignore_error) {
        *cmd_buf += " ; true";
      }

      if (needs_subshell)
        *cmd_buf += ')';
    }
    return (g_flags.remote_num_jobs || g_flags.goma_dir) && !use_gomacc;
  }

  void EmitDepfile(string* cmd_buf) {
    *cmd_buf += ' ';
    string depfile;
    bool result = GetDepfileFromCommand(cmd_buf, &depfile);
    cmd_buf->resize(cmd_buf->size()-1);
    if (!result)
      return;
    fprintf(fp_, " depfile = %s\n", depfile.c_str());
    fprintf(fp_, " deps = gcc\n");
  }

  void EmitNode(DepNode* node) {
    auto p = done_.insert(node->output);
    if (!p.second)
      return;

    // A hack to exclude out phony target in Android. If this exists,
    // "ninja -t clean" tries to remove this directory and fails.
    if (g_flags.detect_android_echo && node->output.str() == "out")
      return;

    // This node is a leaf node
    if (!node->has_rule && !node->is_phony) {
      return;
    }

    vector<Command*> commands;
    ce_.Eval(node, &commands);

    string rule_name = "phony";
    bool use_local_pool = false;
    if (!commands.empty()) {
      rule_name = GenRuleName();
      fprintf(fp_, "rule %s\n", rule_name.c_str());

      string description = "build $out";
      string cmd_buf;
      use_local_pool |= GenShellScript(commands, &cmd_buf, &description);
      fprintf(fp_, " description = %s\n", description.c_str());
      EmitDepfile(&cmd_buf);

      // It seems Linux is OK with ~130kB and Mac's limit is ~250kB.
      // TODO: Find this number automatically.
      if (cmd_buf.size() > 100 * 1000) {
        fprintf(fp_, " rspfile = $out.rsp\n");
        fprintf(fp_, " rspfile_content = %s\n", cmd_buf.c_str());
        fprintf(fp_, " command = %s $out.rsp\n", shell_.c_str());
      } else {
        EscapeShell(&cmd_buf);
        fprintf(fp_, " command = %s -c \"%s\"\n",
                shell_.c_str(), cmd_buf.c_str());
      }
    }

    EmitBuild(node, rule_name);
    if (use_local_pool)
      fprintf(fp_, " pool = local_pool\n");

    for (DepNode* d : node->deps) {
      EmitNode(d);
    }
    for (DepNode* d : node->order_onlys) {
      EmitNode(d);
    }
  }

  string EscapeBuildTarget(Symbol s) const {
    if (s.str().find_first_of("$: ") == string::npos)
      return s.str();
    string r;
    for (char c : s.str()) {
      switch (c) {
        case '$':
        case ':':
        case ' ':
          r += '$';
          // fall through.
        default:
          r += c;
      }
    }
    return r;
  }

  void EscapeShell(string* s) const {
    if (s->find_first_of("$`!\\\"") == string::npos)
      return;
    string r;
    bool last_dollar = false;
    for (char c : *s) {
      switch (c) {
        case '$':
          if (last_dollar) {
            r += c;
            last_dollar = false;
          } else {
            r += '\\';
            r += c;
            last_dollar = true;
          }
          break;
        case '`':
        case '"':
        case '!':
        case '\\':
          r += '\\';
          // fall through.
        default:
          r += c;
          last_dollar = false;
      }
    }
    s->swap(r);
  }

  void EmitBuild(DepNode* node, const string& rule_name) {
    fprintf(fp_, "build %s: %s",
            EscapeBuildTarget(node->output).c_str(),
            rule_name.c_str());
    vector<Symbol> order_onlys;
    if (node->is_phony) {
      fprintf(fp_, " _kati_always_build_");
    }
    for (DepNode* d : node->deps) {
      fprintf(fp_, " %s", EscapeBuildTarget(d->output).c_str());
    }
    if (!node->order_onlys.empty()) {
      fprintf(fp_, " ||");
      for (DepNode* d : node->order_onlys) {
        fprintf(fp_, " %s", EscapeBuildTarget(d->output).c_str());
      }
    }
    fprintf(fp_, "\n");
  }

  void EmitRegenRules(const string& orig_args) {
    if (!g_flags.gen_regen_rule)
      return;

    fprintf(fp_, "rule regen_ninja\n");
    fprintf(fp_, " command = %s\n", orig_args.c_str());
    fprintf(fp_, " generator = 1\n");
    fprintf(fp_, " description = Regenerate ninja files due to dependency\n");
    fprintf(fp_, "build %s: regen_ninja", GetNinjaFilename().c_str());
    unordered_set<string> makefiles;
    MakefileCacheManager::Get()->GetAllFilenames(&makefiles);
    for (const string& makefile : makefiles) {
      fprintf(fp_, " %.*s", SPF(makefile));
    }
    fprintf(fp_, " %s", kati_binary_.c_str());
    fprintf(fp_, "\n\n");
  }

  string GetNinjaFilename() const {
    return StringPrintf("%s/build%s.ninja",
                        ninja_dir_.c_str(), ninja_suffix_.c_str());
  }

  string GetShellScriptFilename() const {
    return StringPrintf("%s/ninja%s.sh",
                        ninja_dir_.c_str(), ninja_suffix_.c_str());
  }

  string GetStampFilename() const {
    return GetStampFilename(ninja_dir_.c_str(), ninja_suffix_.c_str());
  }

  void GenerateNinja(const vector<DepNode*>& nodes,
                     bool build_all_targets,
                     const string& orig_args) {
    fp_ = fopen(GetNinjaFilename().c_str(), "wb");
    if (fp_ == NULL)
      PERROR("fopen(build.ninja) failed");

    fprintf(fp_, "# Generated by kati %s\n", kGitVersion);
    fprintf(fp_, "\n");

    if (!used_envs_.empty()) {
      fprintf(fp_, "# Environment variables used:\n");
      for (const auto& p : used_envs_) {
        fprintf(fp_, "# %s=%s\n", p.first.c_str(), p.second.c_str());
      }
      fprintf(fp_, "\n");
    }

    if (ninja_dir_ != ".") {
      fprintf(fp_, "builddir = %s\n\n", ninja_dir_.c_str());
    }

    fprintf(fp_, "pool local_pool\n");
    fprintf(fp_, " depth = %d\n\n", g_flags.num_jobs);

    fprintf(fp_, "build _kati_always_build_: phony\n\n");

    EmitRegenRules(orig_args);

    for (DepNode* node : nodes) {
      EmitNode(node);
    }

    for (Symbol e : Vars::used_env_vars()) {
      StringPiece val(getenv(e.c_str()));
      used_envs_.emplace(e.str(), val.as_string());
    }

    if (!build_all_targets) {
      CHECK(!nodes.empty());
      fprintf(fp_, "\ndefault %s\n",
              EscapeBuildTarget(nodes.front()->output).c_str());
    }

    fclose(fp_);
  }

  void GenerateShell() {
    FILE* fp = fopen(GetShellScriptFilename().c_str(), "wb");
    if (fp == NULL)
      PERROR("fopen(ninja.sh) failed");

    fprintf(fp, "#!/bin/sh\n");
    fprintf(fp, "# Generated by kati %s\n", kGitVersion);
    fprintf(fp, "\n");
    if (ninja_dir_ == ".")
      fprintf(fp, "cd $(dirname \"$0\")\n");

    for (const auto& p : ev_->exports()) {
      if (p.second) {
        const string val = ev_->EvalVar(p.first);
        fprintf(fp, "export '%s'='%s'\n", p.first.c_str(), val.c_str());
      } else {
        fprintf(fp, "unset '%s'\n", p.first.c_str());
      }
    }

    fprintf(fp, "exec ninja -f %s ", GetNinjaFilename().c_str());
    if (g_flags.remote_num_jobs > 0) {
      fprintf(fp, "-j%d ", g_flags.remote_num_jobs);
    } else if (g_flags.goma_dir) {
      fprintf(fp, "-j500 ");
    }
    fprintf(fp, "\"$@\"\n");

    if (chmod(GetShellScriptFilename().c_str(), 0755) != 0)
      PERROR("chmod ninja.sh failed");
  }

  void GenerateStamp(const string& orig_args) {
    FILE* fp = fopen(GetStampFilename().c_str(), "wb");
    CHECK(fp);

    size_t r = fwrite(&start_time_, sizeof(start_time_), 1, fp);
    CHECK(r == 1);

    unordered_set<string> makefiles;
    MakefileCacheManager::Get()->GetAllFilenames(&makefiles);
    DumpInt(fp, makefiles.size() + 1);
    DumpString(fp, kati_binary_);
    for (const string& makefile : makefiles) {
      DumpString(fp, makefile);
    }

    DumpInt(fp, Evaluator::used_undefined_vars().size());
    for (Symbol v : Evaluator::used_undefined_vars()) {
      DumpString(fp, v.str());
    }

    DumpInt(fp, used_envs_.size());
    for (const auto& p : used_envs_) {
      DumpString(fp, p.first);
      DumpString(fp, p.second);
    }

    const unordered_map<string, vector<string>*>& globs = GetAllGlobCache();
    DumpInt(fp, globs.size());
    for (const auto& p : globs) {
      DumpString(fp, p.first);
      const vector<string>& files = *p.second;
#if 0
      unordered_set<string> dirs;
      GetReadDirs(p.first, files, &dirs);
      DumpInt(fp, dirs.size());
      for (const string& dir : dirs) {
        DumpString(fp, dir);
      }
#endif
      DumpInt(fp, files.size());
      for (const string& file : files) {
        DumpString(fp, file);
      }
    }

    const vector<CommandResult*>& crs = GetShellCommandResults();
    DumpInt(fp, crs.size());
    for (CommandResult* cr : crs) {
      DumpString(fp, cr->cmd);
      DumpString(fp, cr->result);
      if (!cr->find.get()) {
        // Always re-run this command.
        DumpInt(fp, 0);
        continue;
      }

      DumpInt(fp, 1);

      vector<string> missing_dirs;
      for (StringPiece fd : cr->find->finddirs) {
        const string& d = ConcatDir(cr->find->chdir, fd);
        if (!Exists(d))
          missing_dirs.push_back(d);
      }
      DumpInt(fp, missing_dirs.size());
      for (const string& d : missing_dirs) {
        DumpString(fp, d);
      }

      DumpInt(fp, cr->find->read_dirs->size());
      for (StringPiece s : *cr->find->read_dirs) {
        DumpString(fp, ConcatDir(cr->find->chdir, s));
      }
    }

    DumpString(fp, orig_args);

    fclose(fp);
  }

  CommandEvaluator ce_;
  Evaluator* ev_;
  FILE* fp_;
  unordered_set<Symbol> done_;
  int rule_id_;
  string gomacc_;
  string ninja_suffix_;
  string ninja_dir_;
  string shell_;
  map<string, string> used_envs_;
  string kati_binary_;
  double start_time_;
};

void GenerateNinja(const char* ninja_suffix,
                   const char* ninja_dir,
                   const vector<DepNode*>& nodes,
                   Evaluator* ev,
                   bool build_all_targets,
                   const string& orig_args,
                   double start_time) {
  NinjaGenerator ng(ninja_suffix, ninja_dir, ev, start_time);
  ng.Generate(nodes, build_all_targets, orig_args);
}

static bool ShouldIgnoreDirty(StringPiece s) {
  return (g_flags.ignore_dirty_pattern &&
          Pattern(g_flags.ignore_dirty_pattern).Match(s));
}

bool NeedsRegen(const char* ninja_suffix,
                const char* ninja_dir,
                bool ignore_kati_binary,
                bool dump_kati_stamp,
                double start_time,
                const string& orig_args) {
  bool retval = false;
#define RETURN_TRUE do {                         \
    if (dump_kati_stamp)                         \
      retval = true;                             \
    else                                         \
      return true;                               \
  } while (0)

#define LOAD_INT(fp) ({                                                 \
      int v = LoadInt(fp);                                              \
      if (v < 0) {                                                      \
        fprintf(stderr, "incomplete kati_stamp, regenerating...\n");    \
        RETURN_TRUE;                                                    \
      }                                                                 \
      v;                                                                \
    })

#define LOAD_STRING(fp, s) ({                                           \
      if (!LoadString(fp, s)) {                                         \
        fprintf(stderr, "incomplete kati_stamp, regenerating...\n");    \
        RETURN_TRUE;                                                    \
      }                                                                 \
    })

  const string& stamp_filename =
      NinjaGenerator::GetStampFilename(ninja_dir, ninja_suffix);
  FILE* fp = fopen(stamp_filename.c_str(), "rb+");
  if (!fp)
    RETURN_TRUE;
  ScopedFile sfp(fp);

  double gen_time;
  size_t r = fread(&gen_time, sizeof(gen_time), 1, fp);
  if (r != 1) {
    fprintf(stderr, "incomplete kati_stamp, regenerating...\n");
    RETURN_TRUE;
  }
  if (dump_kati_stamp)
    printf("Generated time: %f\n", gen_time);

  string s, s2;
  int num_files = LOAD_INT(fp);
  for (int i = 0; i < num_files; i++) {
    LOAD_STRING(fp, &s);
    double ts = GetTimestamp(s);
    if (gen_time < ts) {
      if (ignore_kati_binary) {
        string kati_binary;
        GetExecutablePath(&kati_binary);
        if (s == kati_binary) {
          fprintf(stderr, "%s was modified, ignored.\n", s.c_str());
          continue;
        }
      }
      if (ShouldIgnoreDirty(s)) {
        if (dump_kati_stamp)
          printf("file %s: ignored (%f)\n", s.c_str(), ts);
        continue;
      }
      if (dump_kati_stamp)
        printf("file %s: dirty (%f)\n", s.c_str(), ts);
      else
        fprintf(stderr, "%s was modified, regenerating...\n", s.c_str());
      RETURN_TRUE;
    } else if (dump_kati_stamp) {
      printf("file %s: clean (%f)\n", s.c_str(), ts);
    }
  }

  int num_undefineds = LOAD_INT(fp);
  for (int i = 0; i < num_undefineds; i++) {
    LOAD_STRING(fp, &s);
    if (getenv(s.c_str())) {
      if (dump_kati_stamp) {
        printf("env %s: dirty (unset => %s)\n", s.c_str(), getenv(s.c_str()));
      } else {
        fprintf(stderr, "Environment variable %s was set, regenerating...\n",
                s.c_str());
      }
      RETURN_TRUE;
    } else if (dump_kati_stamp) {
      printf("env %s: clean (unset)\n", s.c_str());
    }
  }

  int num_envs = LOAD_INT(fp);
  for (int i = 0; i < num_envs; i++) {
    LOAD_STRING(fp, &s);
    StringPiece val(getenv(s.c_str()));
    LOAD_STRING(fp, &s2);
    if (val != s2) {
      if (dump_kati_stamp) {
        printf("env %s: dirty (%s => %.*s)\n",
               s.c_str(), s2.c_str(), SPF(val));
      } else {
        fprintf(stderr, "Environment variable %s was modified (%s => %.*s), "
                "regenerating...\n",
                s.c_str(), s2.c_str(), SPF(val));
      }
      RETURN_TRUE;
    } else if (dump_kati_stamp) {
      printf("env %s: clean (%.*s)\n", s.c_str(), SPF(val));
    }
  }

  {
    int num_globs = LOAD_INT(fp);
    string pat;
    for (int i = 0; i < num_globs; i++) {
      COLLECT_STATS("glob time (regen)");
      LOAD_STRING(fp, &pat);
#if 0
      bool needs_reglob = false;
      int num_dirs = LOAD_INT(fp);
      for (int j = 0; j < num_dirs; j++) {
        LOAD_STRING(fp, &s);
        // TODO: Handle removed files properly.
        needs_reglob |= gen_time < GetTimestamp(s);
      }
#endif
      int num_files = LOAD_INT(fp);
      vector<string>* files;
      Glob(pat.c_str(), &files);
      sort(files->begin(), files->end());
      bool needs_regen = files->size() != static_cast<size_t>(num_files);
      for (int j = 0; j < num_files; j++) {
        LOAD_STRING(fp, &s);
        if (!needs_regen) {
          if ((*files)[j] != s) {
            needs_regen = true;
            break;
          }
        }
      }
      if (needs_regen) {
        if (ShouldIgnoreDirty(pat)) {
          if (dump_kati_stamp) {
            printf("wildcard %s: ignored\n", pat.c_str());
          }
          continue;
        }
        if (dump_kati_stamp) {
          printf("wildcard %s: dirty\n", pat.c_str());
        } else {
          fprintf(stderr, "wildcard(%s) was changed, regenerating...\n",
                  pat.c_str());
        }
        RETURN_TRUE;
      } else if (dump_kati_stamp) {
        printf("wildcard %s: clean\n", pat.c_str());
      }
    }
  }

  int num_crs = LOAD_INT(fp);
  for (int i = 0; i < num_crs; i++) {
    string cmd, expected;
    LOAD_STRING(fp, &cmd);
    LOAD_STRING(fp, &expected);

    {
      COLLECT_STATS("stat time (regen)");
      bool has_condition = LOAD_INT(fp);
      if (has_condition) {
        bool should_run_command = false;

        int num_missing_dirs = LOAD_INT(fp);
        for (int j = 0; j < num_missing_dirs; j++) {
          LOAD_STRING(fp, &s);
          should_run_command |= Exists(s);
        }

        int num_read_dirs = LOAD_INT(fp);
        for (int j = 0; j < num_read_dirs; j++) {
          LOAD_STRING(fp, &s);
          // We assume we rarely do a significant change for the top
          // directory which affects the results of find command.
          if (s == "" || s == "." || ShouldIgnoreDirty(s))
            continue;
          double ts = GetTimestamp(s);
          should_run_command |= (ts < 0 || gen_time < ts);
        }

        if (!should_run_command) {
          if (dump_kati_stamp)
            printf("shell %s: clean (no rerun)\n", cmd.c_str());
          continue;
        }
      }
    }

    FindCommand fc;
    if (fc.Parse(cmd) && !fc.chdir.empty() && ShouldIgnoreDirty(fc.chdir)) {
      if (dump_kati_stamp)
        printf("shell %s: ignored\n", cmd.c_str());
      continue;
    }

    {
      COLLECT_STATS_WITH_SLOW_REPORT("shell time (regen)", cmd.c_str());
      string result;
      RunCommand("/bin/sh", cmd, RedirectStderr::DEV_NULL, &result);
      FormatForCommandSubstitution(&result);
      if (expected != result) {
        if (dump_kati_stamp) {
          printf("shell %s: dirty\n", cmd.c_str());
        } else {
          fprintf(stderr, "$(shell %s) was changed, regenerating...\n",
                  cmd.c_str());
#if 0
          fprintf(stderr, "%s => %s\n",
                  expected.c_str(), result.c_str());
#endif
        }
        RETURN_TRUE;
      } else if (dump_kati_stamp) {
        printf("shell %s: clean (rerun)\n", cmd.c_str());
      }
    }
  }

  LoadString(fp, &s);
  if (orig_args != s) {
    fprintf(stderr, "arguments changed, regenerating...\n");
    RETURN_TRUE;
  }

  if (!retval) {
    if (fseek(fp, 0, SEEK_SET) < 0)
      PERROR("fseek");
    size_t r = fwrite(&start_time, sizeof(start_time), 1, fp);
    CHECK(r == 1);
  }

  return retval;
}