update_engine: Sort full operations by destination.

The inplace generator moves all the full operations to the end of the
list. This patch sorts those operations by the destination.

This patch also cleans up the Vertex class by using the new
AnnotatedOperation class instead of the operation and file_name
separated.

BUG=None
TEST=Unittest still pass. minor_version=1 full operations appear in
order according to "cros payload".

Change-Id: Ia0c15939086cec52dc855cbc3afa913f8cbebf6b
Reviewed-on: https://chromium-review.googlesource.com/286213
Tested-by: Alex Deymo <deymo@chromium.org>
Reviewed-by: Gilad Arnold <garnold@chromium.org>
Commit-Queue: Alex Deymo <deymo@chromium.org>

10 files changed, 160 insertions, 137 deletions

diff --git a/payload_generator/ab_generator.cc b/payload_generator/ab_generator.cc
index 67163eba..2b379e12 100644
--- a/payload_generator/ab_generator.cc
+++ b/payload_generator/ab_generator.cc
@@ -16,28 +16,10 @@
 #include "update_engine/utils.h"
 
 using std::string;
-using std::unique_ptr;
 using std::vector;
 
 namespace chromeos_update_engine {
 
-namespace {
-
-// Compare two AnnotatedOperations by the start block of the first Extent in
-// their destination extents.
-bool CompareAopsByDestination(AnnotatedOperation first_aop,
-                              AnnotatedOperation second_aop) {
-  // We want empty operations to be at the end of the payload.
-  if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size())
-    return ((!first_aop.op.dst_extents().size()) <
-            (!second_aop.op.dst_extents().size()));
-  uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block();
-  uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block();
-  return first_dst_start < second_dst_start;
-}
-
-}  // namespace
-
 bool ABGenerator::GenerateOperations(
     const PayloadGenerationConfig& config,
     int data_file_fd,
@@ -99,7 +81,7 @@ bool ABGenerator::GenerateOperations(
 
 void ABGenerator::SortOperationsByDestination(
     vector<AnnotatedOperation>* aops) {
-  sort(aops->begin(), aops->end(), CompareAopsByDestination);
+  sort(aops->begin(), aops->end(), diff_utils::CompareAopsByDestination);
 }
 
 bool ABGenerator::FragmentOperations(
diff --git a/payload_generator/cycle_breaker.cc b/payload_generator/cycle_breaker.cc
index 906502d3..9c20813e 100644
--- a/payload_generator/cycle_breaker.cc
+++ b/payload_generator/cycle_breaker.cc
@@ -43,7 +43,7 @@ void CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) {
   skipped_ops_ = 0;
 
   for (Graph::size_type i = 0; i < subgraph_.size(); i++) {
-    DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].op.type();
+    DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].aop.op.type();
     if (op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
         op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
       skipped_ops_++;
diff --git a/payload_generator/cycle_breaker_unittest.cc b/payload_generator/cycle_breaker_unittest.cc
index b58bb087..66a13a5c 100644
--- a/payload_generator/cycle_breaker_unittest.cc
+++ b/payload_generator/cycle_breaker_unittest.cc
@@ -25,8 +25,8 @@ namespace chromeos_update_engine {
 
 namespace {
 void SetOpForNodes(Graph* graph) {
-  for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
-    it->op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+  for (Vertex& vertex : *graph) {
+    vertex.aop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
   }
 }
 }  // namespace
@@ -249,8 +249,10 @@ TEST(CycleBreakerTest, SkipOpsTest) {
 
   Graph graph(kNodeCount);
   SetOpForNodes(&graph);
-  graph[n_a].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-  graph[n_c].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+  graph[n_a].aop.op.set_type(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  graph[n_c].aop.op.set_type(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE);
 
   graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
   graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 1));
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index 2d56b680..cfeb867c 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -671,6 +671,17 @@ bool InitializePartitionInfo(const PartitionConfig& part, PartitionInfo* info) {
   return true;
 }
 
+bool CompareAopsByDestination(AnnotatedOperation first_aop,
+                              AnnotatedOperation second_aop) {
+  // We want empty operations to be at the end of the payload.
+  if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size())
+    return ((!first_aop.op.dst_extents().size()) <
+            (!second_aop.op.dst_extents().size()));
+  uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block();
+  uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block();
+  return first_dst_start < second_dst_start;
+}
+
 }  // namespace diff_utils
 
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
index d85249df..0c899a8f 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -111,6 +111,11 @@ void FilterNoopOperations(std::vector<AnnotatedOperation>* ops);
 bool InitializePartitionInfo(const PartitionConfig& partition,
                              PartitionInfo* info);
 
+// Compare two AnnotatedOperations by the start block of the first Extent in
+// their destination extents.
+bool CompareAopsByDestination(AnnotatedOperation first_aop,
+                              AnnotatedOperation second_aop);
+
 }  // namespace diff_utils
 
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/graph_types.h b/payload_generator/graph_types.h
index 7b20bb53..16572b46 100644
--- a/payload_generator/graph_types.h
+++ b/payload_generator/graph_types.h
@@ -13,6 +13,7 @@
 
 #include <base/macros.h>
 
+#include "update_engine/payload_generator/annotated_operation.h"
 #include "update_engine/payload_generator/extent_utils.h"
 #include "update_engine/update_metadata.pb.h"
 
@@ -59,8 +60,7 @@ struct Vertex {
   std::vector<Vertex>::size_type lowlink;
 
   // Other Vertex properties:
-  DeltaArchiveManifest_InstallOperation op;
-  std::string file_name;
+  AnnotatedOperation aop;
 
   typedef std::vector<Vertex>::size_type Index;
   static const Vertex::Index kInvalidIndex;
diff --git a/payload_generator/graph_utils.cc b/payload_generator/graph_utils.cc
index 91665606..265177fc 100644
--- a/payload_generator/graph_utils.cc
+++ b/payload_generator/graph_utils.cc
@@ -114,12 +114,12 @@ void DumpGraph(const Graph& graph) {
   for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) {
     LOG(INFO) << i
               << (graph[i].valid ? "" : "-INV")
-              << ": " << graph[i].file_name
-              << ": " << InstallOperationTypeName(graph[i].op.type());
+              << ": " << graph[i].aop.name
+              << ": " << InstallOperationTypeName(graph[i].aop.op.type());
     LOG(INFO) << "  src_extents:";
-    DumpExtents(graph[i].op.src_extents(), 4);
+    DumpExtents(graph[i].aop.op.src_extents(), 4);
     LOG(INFO) << "  dst_extents:";
-    DumpExtents(graph[i].op.dst_extents(), 4);
+    DumpExtents(graph[i].aop.op.dst_extents(), 4);
     LOG(INFO) << "  out edges:";
     DumpOutEdges(graph[i].out_edges);
   }
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index 6d7df3c1..a142449b 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -27,13 +27,14 @@ using std::map;
 using std::pair;
 using std::set;
 using std::string;
-using std::unique_ptr;
 using std::vector;
 
 namespace chromeos_update_engine {
 
 using Block = InplaceGenerator::Block;
 
+namespace {
+
 // This class allocates non-existent temp blocks, starting from
 // kTempBlockStart. Other code is responsible for converting these
 // temp blocks into real blocks, as the client can't read or write to
@@ -62,9 +63,28 @@ vector<Extent> CompressExtents(const vector<uint64_t>& blocks) {
   return new_extents;
 }
 
+// Helper class to compare two operations by start block of the first Extent in
+// their destination extents given the index of the operations in the graph.
+class IndexedInstallOperationsDstComparator {
+ public:
+  explicit IndexedInstallOperationsDstComparator(Graph* graph)
+    : graph_(graph) {}
+
+  // Compares the operations in the vertex a and b of graph_.
+  bool operator()(size_t a, size_t b) const {
+    return diff_utils::CompareAopsByDestination((*graph_)[a].aop,
+                                                (*graph_)[b].aop);
+  }
+
+ private:
+  const Graph* const graph_;
+};
+
+}  // namespace
+
 void InplaceGenerator::CheckGraph(const Graph& graph) {
   for (const Vertex& v : graph) {
-    CHECK(v.op.has_type());
+    CHECK(v.aop.op.has_type());
   }
 }
 
@@ -74,7 +94,7 @@ void InplaceGenerator::SubstituteBlocks(
     const vector<Extent>& replace_extents) {
   // First, expand out the blocks that op reads from
   vector<uint64_t> read_blocks =
-      ExpandExtents(vertex->op.src_extents());
+      ExpandExtents(vertex->aop.op.src_extents());
   {
     // Expand remove_extents and replace_extents
     vector<uint64_t> remove_extents_expanded = ExpandExtents(remove_extents);
@@ -95,9 +115,9 @@ void InplaceGenerator::SubstituteBlocks(
     }
   }
   // Convert read_blocks back to extents
-  vertex->op.clear_src_extents();
+  vertex->aop.op.clear_src_extents();
   vector<Extent> new_extents = CompressExtents(read_blocks);
-  StoreExtents(new_extents, vertex->op.mutable_src_extents());
+  StoreExtents(new_extents, vertex->aop.op.mutable_src_extents());
 }
 
 bool InplaceGenerator::CutEdges(Graph* graph,
@@ -136,14 +156,15 @@ bool InplaceGenerator::CutEdges(Graph* graph,
                                                     cut_edge_properties));
 
     // Set src/dst extents and other proto variables for copy operation
-    graph->back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+    graph->back().aop.op.set_type(
+        DeltaArchiveManifest_InstallOperation_Type_MOVE);
     StoreExtents(cut_edge_properties.extents,
-                 graph->back().op.mutable_src_extents());
+                 graph->back().aop.op.mutable_src_extents());
     StoreExtents(cuts.back().tmp_extents,
-                 graph->back().op.mutable_dst_extents());
-    graph->back().op.set_src_length(
+                 graph->back().aop.op.mutable_dst_extents());
+    graph->back().aop.op.set_src_length(
         graph_utils::EdgeWeight(*graph, edge) * kBlockSize);
-    graph->back().op.set_dst_length(graph->back().op.src_length());
+    graph->back().aop.op.set_dst_length(graph->back().aop.op.src_length());
 
     // make the dest node read from the scratch space
     SubstituteBlocks(
@@ -235,24 +256,27 @@ void InplaceGenerator::SortCutsByTopoOrder(
   sort(cuts->begin(), cuts->end(), less);
 }
 
-void InplaceGenerator::MoveFullOpsToBack(Graph* graph,
-                                         vector<Vertex::Index>* op_indexes) {
+void InplaceGenerator::MoveAndSortFullOpsToBack(
+    Graph* graph,
+    vector<Vertex::Index>* op_indexes) {
   vector<Vertex::Index> ret;
   vector<Vertex::Index> full_ops;
   ret.reserve(op_indexes->size());
-  for (vector<Vertex::Index>::size_type i = 0, e = op_indexes->size(); i != e;
-       ++i) {
+  for (auto op_index : *op_indexes) {
     DeltaArchiveManifest_InstallOperation_Type type =
-        (*graph)[(*op_indexes)[i]].op.type();
+        (*graph)[op_index].aop.op.type();
     if (type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
         type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
-      full_ops.push_back((*op_indexes)[i]);
+      full_ops.push_back(op_index);
     } else {
-      ret.push_back((*op_indexes)[i]);
+      ret.push_back(op_index);
     }
   }
   LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of "
             << (full_ops.size() + ret.size()) << " total ops.";
+  // Sort full ops according to their dst_extents.
+  sort(full_ops.begin(), full_ops.end(),
+       IndexedInstallOperationsDstComparator(graph));
   ret.insert(ret.end(), full_ops.begin(), full_ops.end());
   op_indexes->swap(ret);
 }
@@ -357,10 +381,10 @@ bool AssignBlockForAdjoiningCuts(
       continue;
     // See if this node has sufficient blocks
     ExtentRanges ranges;
-    ranges.AddRepeatedExtents((*graph)[test_node].op.dst_extents());
+    ranges.AddRepeatedExtents((*graph)[test_node].aop.op.dst_extents());
     ranges.SubtractExtent(ExtentForRange(
         kTempBlockStart, kSparseHole - kTempBlockStart));
-    ranges.SubtractRepeatedExtents((*graph)[test_node].op.src_extents());
+    ranges.SubtractRepeatedExtents((*graph)[test_node].aop.op.src_extents());
     // For now, for simplicity, subtract out all blocks in read-before
     // dependencies.
     for (Vertex::EdgeMap::const_iterator edge_i =
@@ -423,7 +447,8 @@ bool AssignBlockForAdjoiningCuts(
     // Fix the new node w/ the real blocks. Since the new node is just a
     // copy operation, we can replace all the dest extents w/ the real
     // blocks.
-    DeltaArchiveManifest_InstallOperation *op = &(*graph)[cut.new_vertex].op;
+    DeltaArchiveManifest_InstallOperation *op =
+        &(*graph)[cut.new_vertex].aop.op;
     op->clear_dst_extents();
     StoreExtents(real_extents, op->mutable_dst_extents());
   }
@@ -450,7 +475,7 @@ bool InplaceGenerator::AssignTempBlocks(
     LOG(INFO) << "Fixing temp blocks in cut " << i
               << ": old dst: " << cuts[i].old_dst << " new vertex: "
               << cuts[i].new_vertex << " path: "
-              << (*graph)[cuts[i].old_dst].file_name;
+              << (*graph)[cuts[i].old_dst].aop.name;
 
     if (cuts_group.empty() || (cuts_group[0].old_dst == cuts[i].old_dst)) {
       cuts_group.push_back(cuts[i]);
@@ -489,7 +514,7 @@ bool InplaceGenerator::NoTempBlocksRemain(const Graph& graph) {
        ++it, ++idx) {
     if (!it->valid)
       continue;
-    const DeltaArchiveManifest_InstallOperation& op = it->op;
+    const DeltaArchiveManifest_InstallOperation& op = it->aop.op;
     if (TempBlocksExistInExtents(op.dst_extents()) ||
         TempBlocksExistInExtents(op.src_extents())) {
       LOG(INFO) << "bad extents in node " << idx;
@@ -518,9 +543,9 @@ bool InplaceGenerator::ConvertCutToFullOp(Graph* graph,
   // Drop all incoming edges, keep all outgoing edges
 
   // Keep all outgoing edges
-  if ((*graph)[cut.old_dst].op.type() !=
+  if ((*graph)[cut.old_dst].aop.op.type() !=
       DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ &&
-      (*graph)[cut.old_dst].op.type() !=
+      (*graph)[cut.old_dst].aop.op.type() !=
       DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
     Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges;
     graph_utils::DropWriteBeforeDeps(&out_edges);
@@ -529,7 +554,7 @@ bool InplaceGenerator::ConvertCutToFullOp(Graph* graph,
     // |new_extents| list of blocks and update the graph.
     vector<AnnotatedOperation> new_aop;
     vector<Extent> new_extents;
-    ExtentsToVector((*graph)[cut.old_dst].op.dst_extents(),
+    ExtentsToVector((*graph)[cut.old_dst].aop.op.dst_extents(),
                     &new_extents);
     TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFile(
         &new_aop,
@@ -537,7 +562,7 @@ bool InplaceGenerator::ConvertCutToFullOp(Graph* graph,
         new_part,
         vector<Extent>(),  // old_extents
         new_extents,
-        (*graph)[cut.old_dst].file_name,
+        (*graph)[cut.old_dst].aop.name,
         -1,  // chunk_blocks, forces to have a single operation.
         data_fd,
         data_file_size,
@@ -590,7 +615,7 @@ bool InplaceGenerator::ConvertGraphToDag(Graph* graph,
   CheckGraph(*graph);
 
   LOG(INFO) << "Moving full ops to the back";
-  MoveFullOpsToBack(graph, final_order);
+  MoveAndSortFullOpsToBack(graph, final_order);
   LOG(INFO) << "done moving full ops to back";
 
   vector<vector<Vertex::Index>::size_type> inverse_final_order;
@@ -625,11 +650,12 @@ bool InplaceGenerator::ConvertGraphToDag(Graph* graph,
 void InplaceGenerator::CreateScratchNode(uint64_t start_block,
                                          uint64_t num_blocks,
                                          Vertex* vertex) {
-  vertex->file_name = "<scratch>";
-  vertex->op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-  vertex->op.set_data_offset(0);
-  vertex->op.set_data_length(0);
-  Extent* extent = vertex->op.add_dst_extents();
+  vertex->aop.name = "<scratch>";
+  vertex->aop.op.set_type(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  vertex->aop.op.set_data_offset(0);
+  vertex->aop.op.set_data_length(0);
+  Extent* extent = vertex->aop.op.add_dst_extents();
   extent->set_start_block(start_block);
   extent->set_num_blocks(num_blocks);
 }
@@ -661,9 +687,9 @@ bool InplaceGenerator::AddInstallOpToBlocksVector(
           LOG(FATAL) << "Block " << block << " is already "
                      << past_participle << " by "
                      << (*blocks)[block].*access_type << "("
-                     << graph[(*blocks)[block].*access_type].file_name
+                     << graph[(*blocks)[block].*access_type].aop.name
                      << ") and also " << vertex << "("
-                     << graph[vertex].file_name << ")";
+                     << graph[vertex].aop.name << ")";
         }
         (*blocks)[block].*access_type = vertex;
       }
@@ -683,13 +709,13 @@ bool InplaceGenerator::AddInstallOpToGraph(
     graph->emplace_back();
     vertex = graph->size() - 1;
   }
-  (*graph)[vertex].op = operation;
-  CHECK((*graph)[vertex].op.has_type());
-  (*graph)[vertex].file_name = op_name;
+  (*graph)[vertex].aop.op = operation;
+  CHECK((*graph)[vertex].aop.op.has_type());
+  (*graph)[vertex].aop.name = op_name;
 
   if (blocks)
     TEST_AND_RETURN_FALSE(InplaceGenerator::AddInstallOpToBlocksVector(
-        (*graph)[vertex].op,
+        (*graph)[vertex].aop.op,
         *graph,
         vertex,
         blocks));
@@ -753,9 +779,7 @@ bool InplaceGenerator::ResolveReadAfterWriteDependencies(
   aops->reserve(final_order.size());
   for (const Vertex::Index vertex_index : final_order) {
     const Vertex& vertex = graph[vertex_index];
-    aops->emplace_back();
-    aops->back().op = vertex.op;
-    aops->back().name = vertex.file_name;
+    aops->push_back(vertex.aop);
   }
   return true;
 }
diff --git a/payload_generator/inplace_generator.h b/payload_generator/inplace_generator.h
index 54322387..3f8fe500 100644
--- a/payload_generator/inplace_generator.h
+++ b/payload_generator/inplace_generator.h
@@ -103,7 +103,7 @@ class InplaceGenerator : public OperationsGenerator {
   // Given a topologically sorted graph |op_indexes| and |graph|, alters
   // |op_indexes| to move all the full operations to the end of the vector.
   // Full operations should not be depended on, so this is safe.
-  static void MoveFullOpsToBack(Graph* graph,
+  static void MoveAndSortFullOpsToBack(Graph* graph,
                                 std::vector<Vertex::Index>* op_indexes);
 
   // Returns true iff there are no extents in the graph that refer to temp
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
index 5de0df91..65fb132c 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -45,10 +45,10 @@ void GenVertex(Vertex* out,
                const vector<Extent>& dst_extents,
                const string& path,
                DeltaArchiveManifest_InstallOperation_Type type) {
-  out->op.set_type(type);
-  out->file_name = path;
-  StoreExtents(src_extents, out->op.mutable_src_extents());
-  StoreExtents(dst_extents, out->op.mutable_dst_extents());
+  out->aop.op.set_type(type);
+  out->aop.name = path;
+  StoreExtents(src_extents, out->aop.op.mutable_src_extents());
+  StoreExtents(dst_extents, out->aop.op.mutable_dst_extents());
 }
 
 vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
@@ -112,7 +112,7 @@ TEST_F(InplaceGeneratorTest, SubstituteBlocksTest) {
   AppendExtent(&replace_blocks, 10, 2);
   AppendExtent(&replace_blocks, 13, 2);
   Vertex vertex;
-  DeltaArchiveManifest_InstallOperation& op = vertex.op;
+  DeltaArchiveManifest_InstallOperation& op = vertex.aop.op;
   OpAppendExtent(&op, 4, 3);
   OpAppendExtent(&op, kSparseHole, 4);  // Sparse hole in file
   OpAppendExtent(&op, 3, 1);
@@ -144,14 +144,14 @@ TEST_F(InplaceGeneratorTest, CutEdgesTest) {
   // Create nodes in graph
   {
     graph.resize(graph.size() + 1);
-    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+    graph.back().aop.op.set_type(
+        DeltaArchiveManifest_InstallOperation_Type_MOVE);
     // Reads from blocks 3, 5, 7
     vector<Extent> extents;
     AppendBlockToExtents(&extents, 3);
     AppendBlockToExtents(&extents, 5);
     AppendBlockToExtents(&extents, 7);
-    StoreExtents(extents,
-                                     graph.back().op.mutable_src_extents());
+    StoreExtents(extents, graph.back().aop.op.mutable_src_extents());
     blocks[3].reader = graph.size() - 1;
     blocks[5].reader = graph.size() - 1;
     blocks[7].reader = graph.size() - 1;
@@ -161,22 +161,21 @@ TEST_F(InplaceGeneratorTest, CutEdgesTest) {
     AppendBlockToExtents(&extents, 1);
     AppendBlockToExtents(&extents, 2);
     AppendBlockToExtents(&extents, 4);
-    StoreExtents(extents,
-                                     graph.back().op.mutable_dst_extents());
+    StoreExtents(extents, graph.back().aop.op.mutable_dst_extents());
     blocks[1].writer = graph.size() - 1;
     blocks[2].writer = graph.size() - 1;
     blocks[4].writer = graph.size() - 1;
   }
   {
     graph.resize(graph.size() + 1);
-    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+    graph.back().aop.op.set_type(
+        DeltaArchiveManifest_InstallOperation_Type_MOVE);
     // Reads from blocks 1, 2, 4
     vector<Extent> extents;
     AppendBlockToExtents(&extents, 1);
     AppendBlockToExtents(&extents, 2);
     AppendBlockToExtents(&extents, 4);
-    StoreExtents(extents,
-                                     graph.back().op.mutable_src_extents());
+    StoreExtents(extents, graph.back().aop.op.mutable_src_extents());
     blocks[1].reader = graph.size() - 1;
     blocks[2].reader = graph.size() - 1;
     blocks[4].reader = graph.size() - 1;
@@ -186,8 +185,7 @@ TEST_F(InplaceGeneratorTest, CutEdgesTest) {
     AppendBlockToExtents(&extents, 3);
     AppendBlockToExtents(&extents, 5);
     AppendBlockToExtents(&extents, 6);
-    StoreExtents(extents,
-                                     graph.back().op.mutable_dst_extents());
+    StoreExtents(extents, graph.back().aop.op.mutable_dst_extents());
     blocks[3].writer = graph.size() - 1;
     blocks[5].writer = graph.size() - 1;
     blocks[6].writer = graph.size() - 1;
@@ -212,26 +210,26 @@ TEST_F(InplaceGeneratorTest, CutEdgesTest) {
 
   // Check new node in graph:
   EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
-            graph.back().op.type());
-  EXPECT_EQ(2, graph.back().op.src_extents_size());
-  EXPECT_EQ(1, graph.back().op.dst_extents_size());
-  EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
-  EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
+            graph.back().aop.op.type());
+  EXPECT_EQ(2, graph.back().aop.op.src_extents_size());
+  EXPECT_EQ(1, graph.back().aop.op.dst_extents_size());
+  EXPECT_EQ(kTempBlockStart, graph.back().aop.op.dst_extents(0).start_block());
+  EXPECT_EQ(2, graph.back().aop.op.dst_extents(0).num_blocks());
   EXPECT_TRUE(graph.back().out_edges.empty());
 
   // Check that old node reads from new blocks
-  EXPECT_EQ(2, graph[0].op.src_extents_size());
-  EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
-  EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
-  EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
-  EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
+  EXPECT_EQ(2, graph[0].aop.op.src_extents_size());
+  EXPECT_EQ(kTempBlockStart, graph[0].aop.op.src_extents(0).start_block());
+  EXPECT_EQ(2, graph[0].aop.op.src_extents(0).num_blocks());
+  EXPECT_EQ(7, graph[0].aop.op.src_extents(1).start_block());
+  EXPECT_EQ(1, graph[0].aop.op.src_extents(1).num_blocks());
 
   // And that the old dst extents haven't changed
-  EXPECT_EQ(2, graph[0].op.dst_extents_size());
-  EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
-  EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
-  EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
-  EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
+  EXPECT_EQ(2, graph[0].aop.op.dst_extents_size());
+  EXPECT_EQ(1, graph[0].aop.op.dst_extents(0).start_block());
+  EXPECT_EQ(2, graph[0].aop.op.dst_extents(0).num_blocks());
+  EXPECT_EQ(4, graph[0].aop.op.dst_extents(1).start_block());
+  EXPECT_EQ(1, graph[0].aop.op.dst_extents(1).num_blocks());
 
   // Ensure it only depends on the next node and the new temp node
   EXPECT_EQ(2, graph[0].out_edges.size());
@@ -240,17 +238,17 @@ TEST_F(InplaceGeneratorTest, CutEdgesTest) {
                                                                   1));
 
   // Check second node has unchanged extents
-  EXPECT_EQ(2, graph[1].op.src_extents_size());
-  EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
-  EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
-  EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
-  EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
-
-  EXPECT_EQ(2, graph[1].op.dst_extents_size());
-  EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
-  EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
-  EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
-  EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
+  EXPECT_EQ(2, graph[1].aop.op.src_extents_size());
+  EXPECT_EQ(1, graph[1].aop.op.src_extents(0).start_block());
+  EXPECT_EQ(2, graph[1].aop.op.src_extents(0).num_blocks());
+  EXPECT_EQ(4, graph[1].aop.op.src_extents(1).start_block());
+  EXPECT_EQ(1, graph[1].aop.op.src_extents(1).num_blocks());
+
+  EXPECT_EQ(2, graph[1].aop.op.dst_extents_size());
+  EXPECT_EQ(3, graph[1].aop.op.dst_extents(0).start_block());
+  EXPECT_EQ(1, graph[1].aop.op.dst_extents(0).num_blocks());
+  EXPECT_EQ(5, graph[1].aop.op.dst_extents(1).start_block());
+  EXPECT_EQ(2, graph[1].aop.op.dst_extents(1).num_blocks());
 
   // Ensure it only depends on the next node
   EXPECT_EQ(1, graph[1].out_edges.size());
@@ -340,34 +338,35 @@ TEST_F(InplaceGeneratorTest, AssignTempBlocksReuseTest) {
                                                  cuts));
   EXPECT_FALSE(graph[6].valid);
   EXPECT_FALSE(graph[7].valid);
-  EXPECT_EQ(1, graph[1].op.src_extents_size());
-  EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
-  EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
-  EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
+  EXPECT_EQ(1, graph[1].aop.op.src_extents_size());
+  EXPECT_EQ(2, graph[1].aop.op.src_extents(0).start_block());
+  EXPECT_EQ(1, graph[1].aop.op.src_extents(0).num_blocks());
+  EXPECT_EQ(OP_REPLACE_BZ, graph[5].aop.op.type());
 }
 
-TEST_F(InplaceGeneratorTest, MoveFullOpsToBackTest) {
+TEST_F(InplaceGeneratorTest, MoveAndSortFullOpsToBackTest) {
   Graph graph(4);
-  graph[0].file_name = "A";
-  graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-  graph[1].file_name = "B";
-  graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
-  graph[2].file_name = "C";
-  graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-  graph[3].file_name = "D";
-  graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+  graph[0].aop.name = "A";
+  graph[0].aop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+  graph[1].aop.name = "B";
+  graph[1].aop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+  graph[2].aop.name = "C";
+  graph[2].aop.op.set_type(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  graph[3].aop.name = "D";
+  graph[3].aop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
 
   vector<Vertex::Index> vect(graph.size());
 
   for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
     vect[i] = i;
   }
-  InplaceGenerator::MoveFullOpsToBack(&graph, &vect);
+  InplaceGenerator::MoveAndSortFullOpsToBack(&graph, &vect);
   EXPECT_EQ(vect.size(), graph.size());
-  EXPECT_EQ(graph[vect[0]].file_name, "B");
-  EXPECT_EQ(graph[vect[1]].file_name, "D");
-  EXPECT_EQ(graph[vect[2]].file_name, "A");
-  EXPECT_EQ(graph[vect[3]].file_name, "C");
+  EXPECT_EQ(graph[vect[0]].aop.name, "B");
+  EXPECT_EQ(graph[vect[1]].aop.name, "D");
+  EXPECT_EQ(graph[vect[2]].aop.name, "A");
+  EXPECT_EQ(graph[vect[3]].aop.name, "C");
 }
 
 TEST_F(InplaceGeneratorTest, AssignTempBlocksTest) {
@@ -495,12 +494,12 @@ TEST_F(InplaceGeneratorTest, CreateScratchNodeTest) {
   Vertex vertex;
   InplaceGenerator::CreateScratchNode(12, 34, &vertex);
   EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
-            vertex.op.type());
-  EXPECT_EQ(0, vertex.op.data_offset());
-  EXPECT_EQ(0, vertex.op.data_length());
-  EXPECT_EQ(1, vertex.op.dst_extents_size());
-  EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
-  EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
+            vertex.aop.op.type());
+  EXPECT_EQ(0, vertex.aop.op.data_offset());
+  EXPECT_EQ(0, vertex.aop.op.data_length());
+  EXPECT_EQ(1, vertex.aop.op.dst_extents_size());
+  EXPECT_EQ(12, vertex.aop.op.dst_extents(0).start_block());
+  EXPECT_EQ(34, vertex.aop.op.dst_extents(0).num_blocks());
 }
 
 TEST_F(InplaceGeneratorTest, ApplyMapTest) {