# 
# add_file "tests/t_annotate_lineage_dependent.at"
# 
# patch "annotate.cc"
#  from [9a6c5f09fe709c2d8e38f82508bdc1b88871757d]
#    to [8f59e077424facecda91bc5571fd51092e41e967]
# 
# patch "annotate.hh"
#  from [7751f04ac2a92c714e7257de725ce4daeeb505d0]
#    to [c18c25ad6a2f8244aee67bb4948a8eadccafe7c4]
# 
# patch "tests/t_annotate.at"
#  from [a58f8b496e57f594a0c8c7a7f8ac146ddbea1996]
#    to [c41984b9c72ac6a45393a06dfba8f56dd910bf21]
# 
# patch "tests/t_annotate_lineage_dependent.at"
#  from []
#    to [7adce4d02108a140150a8f31470f7ffb23fa0260]
# 
# patch "testsuite.at"
#  from [9d5a9fc124934f2f1ab6415377d8ce12ec54fb37]
#    to [c0d1e4e8f3e1af2aec3dfa734691ce0de6cb945a]
# 
--- annotate.cc
+++ annotate.cc
@@ -80,6 +80,7 @@
 
 class annotate_lineage_mapping;
 
+
 class annotate_context {
 public:
   annotate_context(file_id fid, app_state &app);
@@ -87,7 +88,7 @@
   boost::shared_ptr<annotate_lineage_mapping> initial_lineage() const;
 
   /// credit any remaining unassigned lines to rev
-  void complete(revision_id rev);
+  //void complete(revision_id rev);
 
   /// credit any uncopied lines (as recorded in copied_lines) to
   /// rev, and reset copied_lines.
@@ -97,7 +98,7 @@
   void set_touched(int index);
 
   /// return an immutable reference to our vector of string data for external use
-  const std::vector<std::string>& get_file_lines() const;
+  //const std::vector<std::string>& get_file_lines() const;
 
   /// return true if we have no more unassigned lines
   bool is_complete() const;
@@ -118,7 +119,7 @@
   // similarly, lineages add entries here for all the lines from the UDOI they know about that they didn't copy
   std::set<size_t> touched_lines;
 
-  revision_id root_revision;
+  //revision_id root_revision;
 };
 
 
@@ -133,6 +134,10 @@
   annotate_lineage_mapping(const file_data &data);
   annotate_lineage_mapping(const std::vector<std::string> &lines);
 
+  // debugging
+  bool equal_interned (const annotate_lineage_mapping &rhs) const;
+  bool equal_mapping (const annotate_lineage_mapping &rhs) const;
+
   /// need a better name.  does the work of setting copied bits in the context object.
   boost::shared_ptr<annotate_lineage_mapping> 
   build_parent_lineage(boost::shared_ptr<annotate_context> acp, revision_id parent_rev, const file_data &parent_data) const;
@@ -141,6 +146,9 @@
 
   void set_copied_all_mapped (boost::shared_ptr<annotate_context> acp) const;
 
+  // for debugging
+  void dump_mapped_lines () const;
+
 private:
   void init_with_lines(const std::vector<std::string> &lines);
 
@@ -150,6 +158,12 @@
 
   // same length as file_lines. if file_lines[i] came from line 4 in the UDOI, mapping[i] = 4
   std::vector<int> mapping;
+
+  // for debugging purposes
+  std::vector<revision_id> lineage_traversed;
+  void set_traversed(const std::vector<revision_id> &child_traversed);
+  void add_traversed(const revision_id &r);
+  void dump_traversed() const;
 };
 
 
@@ -213,7 +227,7 @@
   return res;
 }
 
-
+/*
 void 
 annotate_context::complete(revision_id rev)
 {
@@ -226,6 +240,7 @@
     }
   }
 }
+*/
 
 void 
 annotate_context::evaluate(revision_id rev)
@@ -279,14 +294,14 @@
   touched_lines.insert(index);
 }
 
-
+/*
 const std::vector<std::string>& 
 annotate_context::get_file_lines() const
 {
   return file_lines;
 }
+*/
 
-
 bool
 annotate_context::is_complete() const
 {
@@ -332,6 +347,53 @@
   init_with_lines(lines);
 }
 
+bool
+annotate_lineage_mapping::equal_interned (const annotate_lineage_mapping &rhs) const
+{
+  bool result = true;
+
+  if (file_interned.size() != rhs.file_interned.size()) {
+    L(F("annotate_lineage_mapping::equal_interned lhs size %d != rhs size %d\n")
+      % file_interned.size() % rhs.file_interned.size());
+    result = false;
+  }
+
+  size_t limit = std::min(file_interned.size(), rhs.file_interned.size());
+  for (size_t i=0; i<limit; i++) {
+    if (file_interned[i] != rhs.file_interned[i]) {
+      L(F("annotate_lineage_mapping::equal_interned lhs[%d]:%ld != rhs[%d]:%ld\n")
+        % i % file_interned[i] % i % rhs.file_interned[i]);
+      result = false;
+    }
+  }
+
+  return result;
+}
+
+bool
+annotate_lineage_mapping::equal_mapping (const annotate_lineage_mapping &rhs) const
+{
+  bool result = true;
+  L(F("annotate_lineage_mapping::equal_mapping\n"));
+
+  if (mapping.size() != rhs.mapping.size()) {
+    L(F("annotate_lineage_mapping::equal_mapping lhs size %d != rhs size %d\n") 
+      % mapping.size() % rhs.mapping.size());
+    result = false;
+  }
+
+  size_t limit = std::min(mapping.size(), rhs.mapping.size());
+  for (size_t i=0; i<limit; i++) {
+    if (mapping[i] != rhs.mapping[i]) {
+      L(F("annotate_lineage_mapping::equal_mapping lhs[%d]:%ld != rhs[%d]:%ld\n")
+        % i % mapping[i] % i % rhs.mapping[i]);
+      result = false;
+    }
+  }
+
+  return result;
+}
+
 void
 annotate_lineage_mapping::init_with_lines(const std::vector<std::string> &lines)
 {
@@ -355,7 +417,19 @@
                                                 revision_id parent_rev, 
                                                 const file_data &parent_data) const
 {
+  //bool verbose = ( (parent_rev.inner()().find ("93f47d3e0301a3e2cffcd80b2a64d28657a4ea33") == 0) ||
+  //                 (parent_rev.inner()().find ("f1b0b6a67adcf6162b8c191578b310b5105680e1") == 0));
+
+  bool verbose = true;
+
+  if (parent_rev.inner()().find ("93f47d3e0301a3e2cffcd80b2a64d28657a4ea33") == 0) {
+    L(F("build_parent_lineage for parent 93f47d3e0301a3e2cffcd80b2a64d28657a4ea33 calling dump_traverse\n"));
+    dump_traversed();
+  }
+
   boost::shared_ptr<annotate_lineage_mapping> parent_lineage(new annotate_lineage_mapping(parent_data));
+  parent_lineage->set_traversed (lineage_traversed);
+  parent_lineage->add_traversed (parent_rev);
 
   std::vector<long, QA(long)> lcs;
   std::back_insert_iterator< std::vector<long, QA(long)> > bii(lcs);
@@ -366,8 +440,9 @@
                              std::min(file_interned.size(), parent_lineage->file_interned.size()),
                              std::back_inserter(lcs));
 
-  //L(F("build_parent_lineage: file_lines.size() == %d, parent.file_lines.size() == %d, lcs.size() == %d\n")
-  //  % file_interned.size() % parent_lineage->file_interned.size() % lcs.size());
+  if (verbose)
+    L(F("build_parent_lineage: file_lines.size() == %d, parent.file_lines.size() == %d, lcs.size() == %d\n")
+      % file_interned.size() % parent_lineage->file_interned.size() % lcs.size());
 
   // do the copied lines thing for our annotate_context
   std::vector<long> lcs_src_lines;
@@ -375,7 +450,10 @@
   size_t i, j;
   i = j = 0;
   while (i < file_interned.size() && j < lcs.size()) {
-    //L(F("file_interned[%d]: %ld    lcs[%d]: %ld\n") % i % file_interned[i] % j % lcs[j]);
+    //if (verbose)
+    if (file_interned[i] == 14)
+      L(F("%s file_interned[%d]: %ld\tlcs[%d]: %ld\tmapping[%d]: %ld\n") 
+        % parent_rev % i % file_interned[i] % j % lcs[j] % i % mapping[i]);
 
     if (file_interned[i] == lcs[j]) {
       acp->set_copied(mapping[i]);
@@ -387,7 +465,8 @@
 
     i++;
   }
-  //L(F("loop ended with i: %d, j: %d, lcs.size(): %d\n") % i % j % lcs.size());
+  if (verbose)
+    L(F("loop ended with i: %d, j: %d, lcs.size(): %d\n") % i % j % lcs.size());
   I(j == lcs.size());
 
   // set touched for the rest of the lines in the file
@@ -397,7 +476,8 @@
   }
 
   // determine the mapping for parent lineage
-  //L(F("build_parent_lineage: building mapping now\n"));
+  if (verbose)
+    L(F("build_parent_lineage: building mapping now for parent_rev %s\n") % parent_rev);
   i = j = 0;
   while (i < parent_lineage->file_interned.size() && j < lcs.size()) {
     if (parent_lineage->file_interned[i] == lcs[j]) {
@@ -406,11 +486,19 @@
     } else {
       parent_lineage->mapping[i] = -1;
     }
-    //L(F("mapping[%d] -> %d\n") % i % parent_lineage->mapping[i]);
+    if (verbose)
+      L(F("mapping[%d] -> %d\n") % i % parent_lineage->mapping[i]);
     
     i++;
   }
   I(j == lcs.size());
+  // set mapping for the rest of the lines in the file
+  while (i < parent_lineage->file_interned.size()) {
+    parent_lineage->mapping[i] = -1;
+    if (verbose)
+      L(F("mapping[%d] -> %d\n") % i % parent_lineage->mapping[i]);
+    i++;
+  }
 
   return parent_lineage;
 }
@@ -435,15 +523,48 @@
   }
 }
 
+void 
+annotate_lineage_mapping::dump_mapped_lines () const
+{
+  int i;
+  for (i=0; i < (int)mapping.size(); i++) {
+    std::cout << "mapping[" << i << "] -> " << mapping[i] << std::endl;
+  }
+}
 
+void 
+annotate_lineage_mapping::set_traversed(const std::vector<revision_id> &child_traversed) 
+{
+  lineage_traversed = child_traversed;
+}
+
+void 
+annotate_lineage_mapping::add_traversed(const revision_id &r) 
+{
+  lineage_traversed.push_back(r);
+  L(F("add_traversed added %s to total of %d elements\n") % r % lineage_traversed.size());
+}
+
+void
+annotate_lineage_mapping::dump_traversed() const
+{ 
+  for (std::vector<revision_id>::const_iterator i=lineage_traversed.begin(); i != lineage_traversed.end(); i++) { 
+    //std::cout << boost::str(F("traversed %s\n") % *i) << "\n";
+    L(F("traversed %s\n") % *i);
+  }
+}
+
+
 static void
 do_annotate_node (const annotate_node_work &work_unit, 
                   app_state &app,
                   std::deque<annotate_node_work> &nodes_to_process,
-                  std::set<revision_id> &nodes_seen)
+                  std::map<revision_id, boost::shared_ptr<annotate_lineage_mapping> > &nodes_seen)
+                  //std::set<revision_id> &nodes_seen)
 {
-  //L(F("do_annotate_node for node %s\n") % work_unit.node_revision);
-  nodes_seen.insert(work_unit.node_revision);
+  L(F("do_annotate_node for node %s\n") % work_unit.node_revision);
+  //nodes_seen.insert(work_unit.node_revision);
+  nodes_seen.insert(std::make_pair(work_unit.node_revision, work_unit.lineage));
   revision_id null_revision; // initialized to 0 by default?
 
   int added_in_parent_count = 0;
@@ -487,19 +608,33 @@
       file_data data;
       app.db.get_file_version(parent_fid, data);
 
+      L(F("building parent lineage for parent file %s\n") % parent_fid);
       parent_lineage = work_unit.lineage->build_parent_lineage(work_unit.annotations,
-                                                               work_unit.node_revision,
+                                                               edge_old_revision(i),
                                                                data);
     } else {
+      L(F("parent file identical, set copied all mapped and copy lineage\n"));
       parent_lineage = work_unit.lineage;
       parent_lineage->set_copied_all_mapped(work_unit.annotations);
     }
 
     // if this parent has not yet been queued for processing, create the work unit for it.
-    if (nodes_seen.find(edge_old_revision(i)) == nodes_seen.end()) {
-      nodes_seen.insert(edge_old_revision(i));
+    std::map<revision_id, boost::shared_ptr<annotate_lineage_mapping> >::const_iterator ns;
+    ns = nodes_seen.find(edge_old_revision(i));
+    //if (nodes_seen.find(edge_old_revision(i)) == nodes_seen.end()) {
+    if (ns == nodes_seen.end()) {
+      nodes_seen.insert(std::make_pair(edge_old_revision(i), parent_lineage));
       annotate_node_work newunit(work_unit.annotations, parent_lineage, edge_old_revision(i), parent_fid, parent_fpath);
       nodes_to_process.push_back(newunit);
+    } else {
+      L(F("nodes_seen.find(%s) found one, not adding to nodes_to_process\n") 
+        % edge_old_revision(i));
+      if (!(parent_lineage->equal_interned (*(ns->second)))) {
+        I(false);
+      }
+      if (!(parent_lineage->equal_mapping (*(ns->second)))) {
+        //I(false);
+      }
     }
   }
 
@@ -525,7 +660,8 @@
 
   // build node work unit
   std::deque<annotate_node_work> nodes_to_process;
-  std::set<revision_id> nodes_seen;
+  //std::set<revision_id> nodes_seen;
+  std::map<revision_id, boost::shared_ptr<annotate_lineage_mapping> > nodes_seen;
   annotate_node_work workunit(acp, lineage, rid, fid, fpath);
   nodes_to_process.push_back(workunit);
 
@@ -540,15 +676,4 @@
   }
 
   acp->dump();
-  //boost::shared_ptr<annotation_formatter> frmt(new annotation_text_formatter()); 
-  //write_annotations(acp, frmt); // automatically write to stdout, or make take a stream argument?
 }
-
-
-/*
-void
-write_annotations (boost::shared_ptr<annotate_context> acp, 
-                   boost::shared_ptr<annotation_formatter> frmt) 
-{
-}
-*/
--- annotate.hh
+++ annotate.hh
@@ -11,20 +11,6 @@
 #include "revision.hh"
 #include "app_state.hh"
 
-/*
-class annotation_formatter {
-};
-
-class annotation_text_formatter : public annotation_formatter {
-};
-*/
-
-
 extern void do_annotate (app_state &app, file_path fpath, file_id fid, revision_id rid);
 
-/*
-extern void write_annotations (boost::shared_ptr<annotate_context> acp, 
-                               boost::shared_ptr<annotation_formatter> frmt);
-*/
-
 #endif // defined __ANNOTATE_HH__
--- tests/t_annotate.at
+++ tests/t_annotate.at
@@ -21,6 +21,10 @@
 b
 c
 ])
+ADD_FILE(unchanged, [static
+file
+contents
+])
 COMMIT(testbranch)
 REV0=`BASE_REVISION`
 
@@ -55,6 +59,14 @@
 
 
 #
+# unchanged should have all (3) lines from REV0 
+#
+AT_CHECK(MONOTONE annotate unchanged, [], [stdout], [ignore])
+AT_CHECK(head -n 1 stdout | grep $REV0, [0], [ignore], [ignore])
+AT_CHECK(head -n 2 stdout | tail -n 1 | grep $REV0, [0], [ignore], [ignore])
+AT_CHECK(head -n 3 stdout | tail -n 1 | grep $REV0, [0], [ignore], [ignore])
+
+#
 # annotate bar0 should now be
 # REV1: 0
 # REV2: 11
--- tests/t_annotate_lineage_dependent.at
+++ tests/t_annotate_lineage_dependent.at
@@ -0,0 +1,83 @@
+AT_SETUP([annotate where lineage depends on traversal])
+MONOTONE_SETUP
+
+AT_DATA(foo.A, [a
+b
+c
+d
+e
+])
+
+AT_DATA(foo.B, [x
+b
+p
+d
+e
+])
+
+AT_DATA(foo.C, [a
+b
+q
+d changed in C
+y
+])
+
+# foo.D, the ultimate version, as created by our merge3 hook:
+# a
+# b
+# p
+# d changed in C
+# e
+# added line
+
+AT_DATA(merge.lua, [
+function merge3 (ancestor, left, right)
+        data = "a\nb\np\nd changed in C\ne\nadded line\n"
+        return data
+end
+])
+
+
+AT_CHECK(cp foo.A foo)
+AT_CHECK(MONOTONE add foo, [], [ignore], [ignore])
+COMMIT(testbranch)
+REVA=`BASE_REVISION`
+echo rev letter A $REVA
+
+AT_CHECK(cp foo.B foo)
+COMMIT(testbranch)
+REVB=`BASE_REVISION`
+echo rev letter B $REVB
+
+REVERT_TO($REVA)
+
+AT_CHECK(cp foo.C foo)
+COMMIT(testbranch)
+REVC=`BASE_REVISION`
+echo rev letter C $REVC
+
+AT_CHECK(MONOTONE --rcfile=./merge.lua merge, [], [ignore], [ignore])
+AT_CHECK(MONOTONE update, [], [ignore], [ignore])
+REVD=`BASE_REVISION`
+echo rev letter D $REVD
+
+#
+# annotate foo should now be
+# REVA: a
+# REVA: b
+# REVB: p
+# REVC: d changed in C
+# REVA: e
+# REVD: added line
+#
+
+AT_CHECK(MONOTONE --debug annotate foo, [], [stdout], [stderr])
+
+AT_CHECK(head -n 1 stdout | grep $REVA, [0], [ignore], [ignore])
+AT_CHECK(head -n 2 stdout | tail -n 1 | grep $REVA, [0], [ignore], [ignore])
+AT_CHECK(head -n 3 stdout | tail -n 1 | grep $REVB, [0], [ignore], [ignore])
+AT_CHECK(head -n 4 stdout | tail -n 1 | grep $REVC, [0], [ignore], [ignore])
+AT_CHECK(head -n 5 stdout | tail -n 1 | grep $REVA, [0], [ignore], [ignore])
+AT_CHECK(head -n 6 stdout | tail -n 1 | grep $REVD, [0], [ignore], [ignore])
+
+AT_CLEANUP
--- testsuite.at
+++ testsuite.at
@@ -637,3 +637,4 @@
 m4_include(tests/t_unreadable_MT.at)
 m4_include(tests/t_cvsimport3.at)
 m4_include(tests/t_commit_message_file.at)
+m4_include(tests/t_annotate_lineage_dependent.at)