diff --git a/payload_generator/ab_generator.cc b/payload_generator/ab_generator.cc
index 67163eb..2b379e1 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 @@
 
 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 906502d..9c20813 100644
--- a/payload_generator/cycle_breaker.cc
+++ b/payload_generator/cycle_breaker.cc
@@ -43,7 +43,7 @@
   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 b58bb08..66a13a5 100644
--- a/payload_generator/cycle_breaker_unittest.cc
+++ b/payload_generator/cycle_breaker_unittest.cc
@@ -25,8 +25,8 @@
 
 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 @@
 
   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 2d56b68..cfeb867 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -671,6 +671,17 @@
   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 d85249d..0c899a8 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -111,6 +111,11 @@
 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 7b20bb5..16572b4 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 @@
   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 9166560..265177f 100644
--- a/payload_generator/graph_utils.cc
+++ b/payload_generator/graph_utils.cc
@@ -114,12 +114,12 @@
   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 6d7df3c..a142449 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -27,13 +27,14 @@
 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 @@
   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 @@
     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 @@
     }
   }
   // 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 @@
                                                     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 @@
   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 @@
       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 @@
     // 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 @@
     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 @@
        ++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 @@
   // 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 @@
     // |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 @@
         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 @@
   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 @@
 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 @@
           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 @@
     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 @@
   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 5432238..3f8fe50 100644
--- a/payload_generator/inplace_generator.h
+++ b/payload_generator/inplace_generator.h
@@ -103,7 +103,7 @@
   // 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 5de0df9..65fb132 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -45,10 +45,10 @@
                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 @@
   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 @@
   // 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 @@
     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 @@
     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 @@
 
   // 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 @@
                                                                   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].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].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.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 @@
                                                  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 @@
   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) {