diff --git a/dep.cc b/dep.cc
index b56804f..3993c4a 100644
--- a/dep.cc
+++ b/dep.cc
@@ -338,7 +338,7 @@
 
   ~DepBuilder() {}
 
-  void Build(vector<Symbol> targets, vector<DepNode*>* nodes) {
+  void Build(vector<Symbol> targets, vector<NamedDepNode>* nodes) {
     if (!first_rule_.IsValid()) {
       ERROR("*** No targets.");
     }
@@ -373,7 +373,7 @@
       cur_rule_vars_.reset(new Vars);
       ev_->set_current_scope(cur_rule_vars_.get());
       DepNode* n = BuildPlan(target, Intern(""));
-      nodes->push_back(n);
+      nodes->push_back({target,n});
       ev_->set_current_scope(NULL);
       cur_rule_vars_.reset(NULL);
     }
@@ -775,7 +775,7 @@
 
     for (Symbol input : n->actual_inputs) {
       DepNode* c = BuildPlan(input, output);
-      n->deps.push_back(c);
+      n->deps.push_back({input, c});
 
       if (!n->is_phony && c->is_phony) {
         if (g_flags.werror_real_to_phony) {
@@ -792,7 +792,7 @@
 
     for (Symbol input : n->actual_order_only_inputs) {
       DepNode* c = BuildPlan(input, output);
-      n->order_onlys.push_back(c);
+      n->order_onlys.push_back({input,c});
     }
 
     n->has_rule = true;
@@ -831,7 +831,7 @@
              const vector<const Rule*>& rules,
              const unordered_map<Symbol, Vars*>& rule_vars,
              const vector<Symbol>& targets,
-             vector<DepNode*>* nodes) {
+             vector<NamedDepNode>* nodes) {
   DepBuilder db(ev, rules, rule_vars);
   ScopedTimeReporter tr("make dep (build)");
   db.Build(targets, nodes);
diff --git a/dep.h b/dep.h
index c42b380..7c610fd 100644
--- a/dep.h
+++ b/dep.h
@@ -29,14 +29,17 @@
 class Var;
 class Vars;
 
+typedef pair<Symbol,struct DepNode *> NamedDepNode;
+
 struct DepNode {
   DepNode(Symbol output, bool is_phony, bool is_restat);
+  string DebugString();
 
   Symbol output;
   vector<Value*> cmds;
-  vector<DepNode*> deps;
-  vector<DepNode*> order_onlys;
-  vector<DepNode*> parents;
+  vector<NamedDepNode> deps;
+  vector<NamedDepNode> order_onlys;
+  vector<NamedDepNode> parents;
   bool has_rule;
   bool is_default_target;
   bool is_phony;
@@ -58,6 +61,6 @@
              const vector<const Rule*>& rules,
              const unordered_map<Symbol, Vars*>& rule_vars,
              const vector<Symbol>& targets,
-             vector<DepNode*>* nodes);
+             vector<NamedDepNode>* nodes);
 
 #endif  // DEP_H_
diff --git a/exec.cc b/exec.cc
index aa2bd42..5f7993e 100644
--- a/exec.cc
+++ b/exec.cc
@@ -75,17 +75,17 @@
     }
 
     double latest = kProcessing;
-    for (DepNode* d : n->order_onlys) {
-      if (Exists(d->output.str())) {
+    for (auto const& d : n->order_onlys) {
+      if (Exists(d.second->output.str())) {
         continue;
       }
-      double ts = ExecNode(d, n);
+      double ts = ExecNode(d.second, n);
       if (latest < ts)
         latest = ts;
     }
 
-    for (DepNode* d : n->deps) {
-      double ts = ExecNode(d, n);
+    for (auto const& d : n->deps) {
+      double ts = ExecNode(d.second, n);
       if (latest < ts)
         latest = ts;
     }
@@ -138,14 +138,14 @@
 
 }  // namespace
 
-void Exec(const vector<DepNode*>& roots, Evaluator* ev) {
+void Exec(const vector<NamedDepNode>& roots, Evaluator* ev) {
   unique_ptr<Executor> executor(new Executor(ev));
-  for (DepNode* root : roots) {
-    executor->ExecNode(root, NULL);
+  for (auto const& root : roots) {
+    executor->ExecNode(root.second, NULL);
   }
   if (executor->Count() == 0) {
-    for (DepNode* root : roots) {
-      printf("kati: Nothing to be done for `%s'.\n", root->output.c_str());
+    for (auto const & root : roots) {
+      printf("kati: Nothing to be done for `%s'.\n", root.first.c_str());
     }
   }
 }
diff --git a/exec.h b/exec.h
index 26e4c2c..34fda96 100644
--- a/exec.h
+++ b/exec.h
@@ -18,10 +18,9 @@
 #include <vector>
 
 using namespace std;
-
-struct DepNode;
+#include "dep.h"
 class Evaluator;
 
-void Exec(const vector<DepNode*>& roots, Evaluator* ev);
+void Exec(const vector<NamedDepNode>& roots, Evaluator* ev);
 
 #endif  // EXEC_H_
diff --git a/main.cc b/main.cc
index 037db6e..25edbbc 100644
--- a/main.cc
+++ b/main.cc
@@ -280,7 +280,7 @@
              err->msg.c_str());
   }
 
-  vector<DepNode*> nodes;
+  vector<NamedDepNode> nodes;
   {
     ScopedTimeReporter tr("make dep time");
     MakeDep(ev.get(), ev->rules(), ev->rule_vars(), targets, &nodes);
diff --git a/ninja.cc b/ninja.cc
index ac02e0f..d872fb1 100644
--- a/ninja.cc
+++ b/ninja.cc
@@ -200,7 +200,7 @@
       delete nn;
   }
 
-  void Generate(const vector<DepNode*>& nodes, const string& orig_args) {
+  void Generate(const vector<NamedDepNode>& nodes, const string& orig_args) {
     unlink(GetNinjaStampFilename().c_str());
     PopulateNinjaNodes(nodes);
     GenerateNinja();
@@ -220,10 +220,10 @@
   }
 
  private:
-  void PopulateNinjaNodes(const vector<DepNode*>& nodes) {
+  void PopulateNinjaNodes(const vector<NamedDepNode>& nodes) {
     ScopedTimeReporter tr("ninja gen (eval)");
-    for (DepNode* node : nodes) {
-      PopulateNinjaNode(node);
+    for (auto const& node : nodes) {
+      PopulateNinjaNode(node.second);
     }
   }
 
@@ -248,11 +248,11 @@
     nn->rule_id = nn->commands.empty() ? -1 : rule_id_++;
     nodes_.push_back(nn);
 
-    for (DepNode* d : node->deps) {
-      PopulateNinjaNode(d);
+    for (auto const& d : node->deps) {
+      PopulateNinjaNode(d.second);
     }
-    for (DepNode* d : node->order_onlys) {
-      PopulateNinjaNode(d);
+    for (auto const& d : node->order_onlys) {
+      PopulateNinjaNode(d.second);
     }
   }
 
@@ -557,13 +557,13 @@
     if (node->is_phony) {
       *o << " _kati_always_build_";
     }
-    for (DepNode* d : node->deps) {
-      *o << " " << EscapeBuildTarget(d->output).c_str();
+    for (auto const& d : node->deps) {
+      *o << " " << EscapeBuildTarget(d.first).c_str();
     }
     if (!node->order_onlys.empty()) {
       *o << " ||";
-      for (DepNode* d : node->order_onlys) {
-        *o << " " << EscapeBuildTarget(d->output).c_str();
+      for (auto const& d : node->order_onlys) {
+        *o << " " << EscapeBuildTarget(d.first).c_str();
       }
     }
     *o << "\n";
@@ -812,7 +812,7 @@
   return NinjaGenerator::GetFilename(".kati_stamp%s");
 }
 
-void GenerateNinja(const vector<DepNode*>& nodes,
+void GenerateNinja(const vector<NamedDepNode>& nodes,
                    Evaluator* ev,
                    const string& orig_args,
                    double start_time) {
diff --git a/ninja.h b/ninja.h
index 89683e8..85dab5f 100644
--- a/ninja.h
+++ b/ninja.h
@@ -21,13 +21,13 @@
 #include <vector>
 
 #include "string_piece.h"
+#include "dep.h"
 
 using namespace std;
 
-struct DepNode;
 class Evaluator;
 
-void GenerateNinja(const vector<DepNode*>& nodes,
+void GenerateNinja(const vector<NamedDepNode>& nodes,
                    Evaluator* ev,
                    const string& orig_args,
                    double start_time);
diff --git a/runtest.rb b/runtest.rb
index 7bc552d..1a341f1 100755
--- a/runtest.rb
+++ b/runtest.rb
@@ -342,7 +342,7 @@
 
   run_in_testdir(sh) do |name|
     cleanup
-    cmd = "sh ../../#{sh} make"
+    cmd = "bash ../../#{sh} make"
     if is_ninja_test
       cmd += ' -s'
     end
@@ -352,15 +352,15 @@
 
     if is_ninja_test
       if ckati
-        cmd = "sh ../../#{sh} ../../ckati --ninja --regen"
+        cmd = "bash ../../#{sh} ../../ckati --ninja --regen"
       else
         next
       end
     else
       if ckati
-        cmd = "sh ../../#{sh} ../../ckati"
+        cmd = "bash ../../#{sh} ../../ckati"
       else
-        cmd = "sh ../../#{sh} ../../kati --use_cache -log_dir=."
+        cmd = "bash ../../#{sh} ../../kati --use_cache -log_dir=."
       end
     end
     cmd += bash_var
diff --git a/testcase/ninja_implicit_dependent.sh b/testcase/ninja_implicit_dependent.sh
new file mode 100755
index 0000000..e036032
--- /dev/null
+++ b/testcase/ninja_implicit_dependent.sh
@@ -0,0 +1,48 @@
+#!/bin/bash
+#
+# Copyright 2018 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.
+
+set -e
+mk="$@"
+
+cat <<EOF >Makefile
+all: secondary_dep
+
+secondary_dep: secondary
+	@touch \$@
+	@echo Made \$@
+
+primary: .KATI_IMPLICIT_OUTPUTS := secondary
+primary:
+	@touch primary secondary
+	@echo Made primary+secondary
+EOF
+
+if [[ "${mk}" =~ ^make ]]; then
+  echo Made primary+secondary
+  echo Made secondary_dep
+  echo Made secondary_dep
+  echo Nothing to do
+else
+  ${mk} -j1
+  ./ninja.sh -j1 -w dupbuild=err;
+  sleep 1
+  touch secondary
+  ./ninja.sh -j1 -w dupbuild=err;
+  sleep 1
+  echo Nothing to do
+  touch primary
+  ./ninja.sh -j1 -w dupbuild=err;
+fi