Convert pattern stack from deque to vector, and share it

Also move various vector::reserve calls to State ctor
Negligible perf benefit, but more tidy.

8 files changed, 148 insertions, 134 deletions

diff --git a/source/assembly_grammar.cpp b/source/assembly_grammar.cpp
index 294c07a6..997c4c20 100644
--- a/source/assembly_grammar.cpp
+++ b/source/assembly_grammar.cpp
@@ -234,9 +234,9 @@ spv_result_t AssemblyGrammar::lookupExtInst(spv_ext_inst_type_t type,
   return spvExtInstTableValueLookup(extInstTable_, type, firstWord, extInst);
 }
 
-void AssemblyGrammar::prependOperandTypesForMask(
+void AssemblyGrammar::pushOperandTypesForMask(
     const spv_operand_type_t type, const uint32_t mask,
     spv_operand_pattern_t* pattern) const {
-  spvPrependOperandTypesForMask(operandTable_, type, mask, pattern);
+  spvPushOperandTypesForMask(operandTable_, type, mask, pattern);
 }
 }  // namespace libspirv
diff --git a/source/assembly_grammar.h b/source/assembly_grammar.h
index ac211369..cd89a1b1 100644
--- a/source/assembly_grammar.h
+++ b/source/assembly_grammar.h
@@ -95,17 +95,19 @@ class AssemblyGrammar {
   spv_result_t lookupExtInst(spv_ext_inst_type_t type, uint32_t firstWord,
                              spv_ext_inst_desc* extInst) const;
 
-  // Inserts the operands expected after the given typed mask onto the front
+  // Inserts the operands expected after the given typed mask onto the end
   // of the given pattern.
   //
-  // Each set bit in the mask represents zero or more operand types that should
-  // be prepended onto the pattern. Operands for a less significant bit always
-  // appear before operands for a more significant bit.
+  // Each set bit in the mask represents zero or more operand types that
+  // should be appended onto the pattern. Operands for a less significant
+  // bit must always match before operands for a more significant bit, so
+  // the operands for a less significant bit must appear closer to the end
+  // of the pattern stack.
   //
   // If a set bit is unknown, then we assume it has no operands.
-  void prependOperandTypesForMask(const spv_operand_type_t type,
-                                  const uint32_t mask,
-                                  spv_operand_pattern_t* pattern) const;
+  void pushOperandTypesForMask(const spv_operand_type_t type,
+                               const uint32_t mask,
+                               spv_operand_pattern_t* pattern) const;
 
  private:
   const spv_target_env target_env_;
diff --git a/source/binary.cpp b/source/binary.cpp
index df756323..2ade2546 100644
--- a/source/binary.cpp
+++ b/source/binary.cpp
@@ -178,7 +178,14 @@ class Parser {
           diagnostic(diagnostic_arg),
           word_index(0),
           endian(),
-          requires_endian_conversion(false) {}
+          requires_endian_conversion(false) {
+
+        // Temporary storage for parser state within a single instruction.
+        // Most instructions require fewer than 25 words or operands.
+        operands.reserve(25);
+        endian_converted_words.reserve(25);
+        expected_operands.reserve(25);
+    }
     State() : State(0, 0, nullptr) {}
     const uint32_t* words;       // Words in the binary SPIR-V module.
     size_t num_words;            // Number of words in the module.
@@ -202,6 +209,7 @@ class Parser {
     // Used by parseOperand
     std::vector<spv_parsed_operand_t> operands;
     std::vector<uint32_t> endian_converted_words;
+    spv_operand_pattern_t expected_operands;
   } _;
 };
 
@@ -266,25 +274,15 @@ spv_result_t Parser::parseInstruction() {
 
   const uint32_t first_word = peek();
 
-  // TODO(dneto): If it's too expensive to construct the following "words"
-  // and "operands" vectors for each instruction, each instruction, then make
-  // them class data members instead, and clear them here.
-
   // If the module's endianness is different from the host native endianness,
   // then converted_words contains the the endian-translated words in the
   // instruction.
   _.endian_converted_words.clear();
   _.endian_converted_words.push_back(first_word);
-  if (_.requires_endian_conversion) {
-    // Most instructions have fewer than 25 words.
-    _.endian_converted_words.reserve(25);
-  }
 
   // After a successful parse of the instruction, the inst.operands member
   // will point to this vector's storage.
-  // Most instructions have fewer than 25 logical operands.
   _.operands.clear();
-  _.operands.reserve(25);
 
   assert(_.word_index < _.num_words);
   // Decompose and check the first word.
@@ -310,13 +308,13 @@ spv_result_t Parser::parseInstruction() {
   // has its own logical operands (such as the LocalSize operand for
   // ExecutionMode), or for extended instructions that may have their
   // own operands depending on the selected extended instruction.
-  spv_operand_pattern_t expected_operands(
-      opcode_desc->operandTypes,
-      opcode_desc->operandTypes + opcode_desc->numTypes);
+  _.expected_operands.clear();
+  for (auto i = 0; i < opcode_desc->numTypes; i++)
+      _.expected_operands.push_back(opcode_desc->operandTypes[opcode_desc->numTypes - i - 1]);
 
   while (_.word_index < inst_offset + inst_word_count) {
     const uint16_t inst_word_index = uint16_t(_.word_index - inst_offset);
-    if (expected_operands.empty()) {
+    if (_.expected_operands.empty()) {
       return diagnostic() << "Invalid instruction Op" << opcode_desc->name
                           << " starting at word " << inst_offset
                           << ": expected no more operands after "
@@ -325,17 +323,17 @@ spv_result_t Parser::parseInstruction() {
                           << inst_word_count << ".";
     }
 
-    spv_operand_type_t type = spvTakeFirstMatchableOperand(&expected_operands);
+    spv_operand_type_t type = spvTakeFirstMatchableOperand(&_.expected_operands);
 
     if (auto error =
             parseOperand(inst_offset, &inst, type, &_.endian_converted_words,
-                         &_.operands, &expected_operands)) {
+                         &_.operands, &_.expected_operands)) {
       return error;
     }
   }
 
-  if (!expected_operands.empty() &&
-      !spvOperandIsOptional(expected_operands.front())) {
+  if (!_.expected_operands.empty() &&
+      !spvOperandIsOptional(_.expected_operands.back())) {
     return diagnostic() << "End of input reached while decoding Op"
                         << opcode_desc->name << " starting at word "
                         << inst_offset << ": expected more operands after "
@@ -473,7 +471,7 @@ spv_result_t Parser::parseOperand(size_t inst_offset,
       spv_ext_inst_desc ext_inst;
       if (grammar_.lookupExtInst(inst->ext_inst_type, word, &ext_inst))
         return diagnostic() << "Invalid extended instruction number: " << word;
-      spvPrependOperandTypes(ext_inst->operandTypes, expected_operands);
+      spvPushOperandTypes(ext_inst->operandTypes, expected_operands);
     } break;
 
     case SPV_OPERAND_TYPE_SPEC_CONSTANT_OP_NUMBER: {
@@ -493,7 +491,7 @@ spv_result_t Parser::parseOperand(size_t inst_offset,
       assert(opcode_entry->hasType);
       assert(opcode_entry->hasResult);
       assert(opcode_entry->numTypes >= 2);
-      spvPrependOperandTypes(opcode_entry->operandTypes + 2, expected_operands);
+      spvPushOperandTypes(opcode_entry->operandTypes + 2, expected_operands);
     } break;
 
     case SPV_OPERAND_TYPE_LITERAL_INTEGER:
@@ -627,7 +625,7 @@ spv_result_t Parser::parseOperand(size_t inst_offset,
                             << " operand: " << word;
       }
       // Prepare to accept operands to this operand, if needed.
-      spvPrependOperandTypes(entry->operandTypes, expected_operands);
+      spvPushOperandTypes(entry->operandTypes, expected_operands);
     } break;
 
     case SPV_OPERAND_TYPE_FP_FAST_MATH_MODE:
@@ -662,7 +660,7 @@ spv_result_t Parser::parseOperand(size_t inst_offset,
                    << mask;
           }
           remaining_word ^= mask;
-          spvPrependOperandTypes(entry->operandTypes, expected_operands);
+          spvPushOperandTypes(entry->operandTypes, expected_operands);
         }
       }
       if (word == 0) {
@@ -670,7 +668,7 @@ spv_result_t Parser::parseOperand(size_t inst_offset,
         spv_operand_desc entry;
         if (SPV_SUCCESS == grammar_.lookupOperand(type, 0, &entry)) {
           // Prepare for its operands, if any.
-          spvPrependOperandTypes(entry->operandTypes, expected_operands);
+          spvPushOperandTypes(entry->operandTypes, expected_operands);
         }
       }
     } break;
diff --git a/source/comp/markv_codec.cpp b/source/comp/markv_codec.cpp
index f621d3b3..9a080ee2 100644
--- a/source/comp/markv_codec.cpp
+++ b/source/comp/markv_codec.cpp
@@ -1178,7 +1178,7 @@ spv_result_t MarkvDecoder::DecodeOperand(
       }
 
       // Prepare to accept operands to this operand, if needed.
-      spvPrependOperandTypes(entry->operandTypes, expected_operands);
+      spvPushOperandTypes(entry->operandTypes, expected_operands);
       break;
     }
 
@@ -1221,7 +1221,7 @@ spv_result_t MarkvDecoder::DecodeOperand(
                    << mask;
           }
           remaining_word ^= mask;
-          spvPrependOperandTypes(entry->operandTypes, expected_operands);
+          spvPushOperandTypes(entry->operandTypes, expected_operands);
         }
       }
       if (word == 0) {
@@ -1229,7 +1229,7 @@ spv_result_t MarkvDecoder::DecodeOperand(
         spv_operand_desc entry;
         if (SPV_SUCCESS == grammar_.lookupOperand(type, 0, &entry)) {
           // Prepare for its operands, if any.
-          spvPrependOperandTypes(entry->operandTypes, expected_operands);
+          spvPushOperandTypes(entry->operandTypes, expected_operands);
         }
       }
       break;
@@ -1287,9 +1287,10 @@ spv_result_t MarkvDecoder::DecodeInstruction(spv_parsed_instruction_t* inst) {
     return vstate_.diag(SPV_ERROR_INVALID_BINARY) << "Invalid opcode";
   }
 
-  spv_operand_pattern_t expected_operands(
-      opcode_desc->operandTypes,
-      opcode_desc->operandTypes + opcode_desc->numTypes);
+  spv_operand_pattern_t expected_operands;
+  expected_operands.reserve(opcode_desc->numTypes);
+  for (auto i = 0; i < opcode_desc->numTypes; i++)
+    expected_operands.push_back(opcode_desc->operandTypes[opcode_desc->numTypes - i - 1]);
 
   if (!OpcodeHasFixedNumberOfOperands(opcode)) {
     if (!reader_.ReadVariableWidthU16(&inst->num_operands,
diff --git a/source/operand.cpp b/source/operand.cpp
index cf234e77..29da94d1 100644
--- a/source/operand.cpp
+++ b/source/operand.cpp
@@ -16,6 +16,7 @@
 
 #include <assert.h>
 #include <string.h>
+#include <algorithm>
 
 #include "macro.h"
 
@@ -218,26 +219,28 @@ const char* spvOperandTypeStr(spv_operand_type_t type) {
   return "unknown";
 }
 
-void spvPrependOperandTypes(const spv_operand_type_t* types,
-                            spv_operand_pattern_t* pattern) {
+void spvPushOperandTypes(const spv_operand_type_t* types,
+                         spv_operand_pattern_t* pattern) {
   const spv_operand_type_t* endTypes;
   for (endTypes = types; *endTypes != SPV_OPERAND_TYPE_NONE; ++endTypes)
     ;
-  pattern->insert(pattern->begin(), types, endTypes);
+  while (endTypes-- != types) {
+      pattern->push_back(*endTypes);
+  }
 }
 
-void spvPrependOperandTypesForMask(const spv_operand_table operandTable,
-                                   const spv_operand_type_t type,
-                                   const uint32_t mask,
-                                   spv_operand_pattern_t* pattern) {
-  // Scan from highest bits to lowest bits because we will prepend in LIFO
-  // fashion, and we need the operands for lower order bits to appear first.
+void spvPushOperandTypesForMask(const spv_operand_table operandTable,
+                                const spv_operand_type_t type,
+                                const uint32_t mask,
+                                spv_operand_pattern_t* pattern) {
+  // Scan from highest bits to lowest bits because we will append in LIFO
+  // fashion, and we need the operands for lower order bits to be consumed first
   for (uint32_t candidate_bit = (1u << 31u); candidate_bit; candidate_bit >>= 1) {
     if (candidate_bit & mask) {
       spv_operand_desc entry = nullptr;
       if (SPV_SUCCESS == spvOperandTableValueLookup(operandTable, type,
                                                     candidate_bit, &entry)) {
-        spvPrependOperandTypes(entry->operandTypes, pattern);
+        spvPushOperandTypes(entry->operandTypes, pattern);
       }
     }
   }
@@ -262,24 +265,25 @@ bool spvExpandOperandSequenceOnce(spv_operand_type_t type,
                                   spv_operand_pattern_t* pattern) {
   switch (type) {
     case SPV_OPERAND_TYPE_VARIABLE_ID:
-      pattern->insert(pattern->begin(), {SPV_OPERAND_TYPE_OPTIONAL_ID, type});
+      pattern->push_back(type);
+      pattern->push_back(SPV_OPERAND_TYPE_OPTIONAL_ID);
       return true;
     case SPV_OPERAND_TYPE_VARIABLE_LITERAL_INTEGER:
-      pattern->insert(pattern->begin(),
-                      {SPV_OPERAND_TYPE_OPTIONAL_LITERAL_INTEGER, type});
+      pattern->push_back(type);
+      pattern->push_back(SPV_OPERAND_TYPE_OPTIONAL_LITERAL_INTEGER);
       return true;
     case SPV_OPERAND_TYPE_VARIABLE_LITERAL_INTEGER_ID:
       // Represents Zero or more (Literal number, Id) pairs,
       // where the literal number must be a scalar integer.
-      pattern->insert(pattern->begin(),
-                      {SPV_OPERAND_TYPE_OPTIONAL_TYPED_LITERAL_INTEGER,
-                       SPV_OPERAND_TYPE_ID, type});
+      pattern->push_back(type);
+      pattern->push_back(SPV_OPERAND_TYPE_ID);
+      pattern->push_back(SPV_OPERAND_TYPE_OPTIONAL_TYPED_LITERAL_INTEGER);
       return true;
     case SPV_OPERAND_TYPE_VARIABLE_ID_LITERAL_INTEGER:
       // Represents Zero or more (Id, Literal number) pairs.
-      pattern->insert(pattern->begin(),
-                      {SPV_OPERAND_TYPE_OPTIONAL_ID,
-                       SPV_OPERAND_TYPE_LITERAL_INTEGER, type});
+      pattern->push_back(type);
+      pattern->push_back(SPV_OPERAND_TYPE_LITERAL_INTEGER);
+      pattern->push_back(SPV_OPERAND_TYPE_OPTIONAL_ID);
       return true;
     default:
       break;
@@ -292,25 +296,24 @@ spv_operand_type_t spvTakeFirstMatchableOperand(
   assert(!pattern->empty());
   spv_operand_type_t result;
   do {
-    result = pattern->front();
-    pattern->pop_front();
+    result = pattern->back();
+    pattern->pop_back();
   } while (spvExpandOperandSequenceOnce(result, pattern));
   return result;
 }
 
 spv_operand_pattern_t spvAlternatePatternFollowingImmediate(
     const spv_operand_pattern_t& pattern) {
-  spv_operand_pattern_t alternatePattern;
-  for (const auto& operand : pattern) {
-    if (operand == SPV_OPERAND_TYPE_RESULT_ID) {
-      alternatePattern.push_back(operand);
-      alternatePattern.push_back(SPV_OPERAND_TYPE_OPTIONAL_CIV);
-      return alternatePattern;
-    }
-    alternatePattern.push_back(SPV_OPERAND_TYPE_OPTIONAL_CIV);
+
+  auto it = std::find(pattern.crbegin(), pattern.crend(), SPV_OPERAND_TYPE_RESULT_ID);
+  if (it != pattern.crend()) {
+    spv_operand_pattern_t alternatePattern(it - pattern.crbegin() + 2, SPV_OPERAND_TYPE_OPTIONAL_CIV);
+    alternatePattern[1] = SPV_OPERAND_TYPE_RESULT_ID;
+    return alternatePattern;
   }
+
   // No result-id found, so just expect CIVs.
-  return {SPV_OPERAND_TYPE_OPTIONAL_CIV};
+  return{ SPV_OPERAND_TYPE_OPTIONAL_CIV };
 }
 
 bool spvIsIdType(spv_operand_type_t type) {
diff --git a/source/operand.h b/source/operand.h
index 5d77a347..fa7c6f2e 100644
--- a/source/operand.h
+++ b/source/operand.h
@@ -26,8 +26,13 @@
 // next on the input.
 //
 // As we parse an instruction in text or binary form from left to right,
-// we pull and push from the front of the pattern.
-using spv_operand_pattern_t = std::deque<spv_operand_type_t>;
+// we pop and push at the end of the pattern vector. Symbols later in the
+// pattern vector are matched against the input before symbols earlier in the
+// pattern vector are matched.
+
+// Using a vector in this way reduces memory traffic, which is good for
+// performance.
+using spv_operand_pattern_t = std::vector<spv_operand_type_t>;
 
 // Finds the named operand in the table. The type parameter specifies the
 // operand's group. A handle of the operand table entry for this operand will
@@ -62,24 +67,24 @@ bool spvOperandIsOptional(spv_operand_type_t type);
 // operand.
 bool spvOperandIsVariable(spv_operand_type_t type);
 
-// Inserts a list of operand types into the front of the given pattern.
+// Append a list of operand types to the end of the pattern vector.
 // The types parameter specifies the source array of types, ending with
 // SPV_OPERAND_TYPE_NONE.
-void spvPrependOperandTypes(const spv_operand_type_t* types,
-                            spv_operand_pattern_t* pattern);
+void spvPushOperandTypes(const spv_operand_type_t* types,
+                         spv_operand_pattern_t* pattern);
 
-// Inserts the operands expected after the given typed mask onto the
-// front of the given pattern.
+// Appends the operands expected after the given typed mask onto the
+// end of the given pattern.
 //
 // Each set bit in the mask represents zero or more operand types that should
-// be prepended onto the pattern.  Operands for a less significant bit always
-// appear before operands for a more significant bit.
+// be appended onto the pattern.  Operands for a less significant bit always
+// appear after operands for a more significant bit.
 //
 // If a set bit is unknown, then we assume it has no operands.
-void spvPrependOperandTypesForMask(const spv_operand_table operand_table,
-                                   const spv_operand_type_t mask_type,
-                                   const uint32_t mask,
-                                   spv_operand_pattern_t* pattern);
+void spvPushOperandTypesForMask(const spv_operand_table operand_table,
+                                const spv_operand_type_t mask_type,
+                                const uint32_t mask,
+                                spv_operand_pattern_t* pattern);
 
 // Expands an operand type representing zero or more logical operands,
 // exactly once.
diff --git a/source/text.cpp b/source/text.cpp
index 6a6846ea..8c48814b 100644
--- a/source/text.cpp
+++ b/source/text.cpp
@@ -247,7 +247,7 @@ spv_result_t spvTextEncodeOperand(const libspirv::AssemblyGrammar& grammar,
       spvInstructionAddWord(pInst, extInst->ext_inst);
 
       // Prepare to parse the operands for the extended instructions.
-      spvPrependOperandTypes(extInst->operandTypes, pExpectedOperands);
+      spvPushOperandTypes(extInst->operandTypes, pExpectedOperands);
     } break;
 
     case SPV_OPERAND_TYPE_SPEC_CONSTANT_OP_NUMBER: {
@@ -271,7 +271,7 @@ spv_result_t spvTextEncodeOperand(const libspirv::AssemblyGrammar& grammar,
       assert(opcodeEntry->hasType);
       assert(opcodeEntry->hasResult);
       assert(opcodeEntry->numTypes >= 2);
-      spvPrependOperandTypes(opcodeEntry->operandTypes + 2, pExpectedOperands);
+      spvPushOperandTypes(opcodeEntry->operandTypes + 2, pExpectedOperands);
     } break;
 
     case SPV_OPERAND_TYPE_LITERAL_INTEGER:
@@ -380,7 +380,7 @@ spv_result_t spvTextEncodeOperand(const libspirv::AssemblyGrammar& grammar,
       }
       if (auto error = context->binaryEncodeU32(value, pInst)) return error;
       // Prepare to parse the operands for this logical operand.
-      grammar.prependOperandTypesForMask(type, value, pExpectedOperands);
+      grammar.pushOperandTypesForMask(type, value, pExpectedOperands);
     } break;
     case SPV_OPERAND_TYPE_OPTIONAL_CIV: {
       auto error = spvTextEncodeOperand(
@@ -420,7 +420,7 @@ spv_result_t spvTextEncodeOperand(const libspirv::AssemblyGrammar& grammar,
       }
 
       // Prepare to parse the operands for this logical operand.
-      spvPrependOperandTypes(entry->operandTypes, pExpectedOperands);
+      spvPushOperandTypes(entry->operandTypes, pExpectedOperands);
     } break;
   }
   return SPV_SUCCESS;
@@ -553,13 +553,14 @@ spv_result_t spvTextEncodeOpcode(const libspirv::AssemblyGrammar& grammar,
   // has its own logical operands (such as the LocalSize operand for
   // ExecutionMode), or for extended instructions that may have their
   // own operands depending on the selected extended instruction.
-  spv_operand_pattern_t expectedOperands(
-      opcodeEntry->operandTypes,
-      opcodeEntry->operandTypes + opcodeEntry->numTypes);
+  spv_operand_pattern_t expectedOperands;
+  expectedOperands.reserve(opcodeEntry->numTypes);
+  for (auto i = 0; i < opcodeEntry->numTypes; i++)
+      expectedOperands.push_back(opcodeEntry->operandTypes[opcodeEntry->numTypes - i - 1]);
 
   while (!expectedOperands.empty()) {
-    const spv_operand_type_t type = expectedOperands.front();
-    expectedOperands.pop_front();
+    const spv_operand_type_t type = expectedOperands.back();
+    expectedOperands.pop_back();
 
     // Expand optional tuples lazily.
     if (spvExpandOperandSequenceOnce(type, &expectedOperands)) continue;
diff --git a/test/operand_pattern_test.cpp b/test/operand_pattern_test.cpp
index be4fffdc..358671c5 100644
--- a/test/operand_pattern_test.cpp
+++ b/test/operand_pattern_test.cpp
@@ -28,31 +28,31 @@ TEST(OperandPattern, InitiallyEmpty) {
   EXPECT_TRUE(empty.empty());
 }
 
-TEST(OperandPattern, PushFrontsAreOnTheLeft) {
+TEST(OperandPattern, PushBacksAreOnTheRight) {
   spv_operand_pattern_t pattern;
 
-  pattern.push_front(SPV_OPERAND_TYPE_ID);
+  pattern.push_back(SPV_OPERAND_TYPE_ID);
   EXPECT_THAT(pattern, Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_ID}));
   EXPECT_EQ(1u, pattern.size());
   EXPECT_TRUE(!pattern.empty());
-  EXPECT_EQ(SPV_OPERAND_TYPE_ID, pattern.front());
+  EXPECT_EQ(SPV_OPERAND_TYPE_ID, pattern.back());
 
-  pattern.push_front(SPV_OPERAND_TYPE_NONE);
-  EXPECT_THAT(pattern, Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_NONE,
-                                                SPV_OPERAND_TYPE_ID}));
+  pattern.push_back(SPV_OPERAND_TYPE_NONE);
+  EXPECT_THAT(pattern, Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_ID,
+                                                SPV_OPERAND_TYPE_NONE}));
   EXPECT_EQ(2u, pattern.size());
   EXPECT_TRUE(!pattern.empty());
-  EXPECT_EQ(SPV_OPERAND_TYPE_NONE, pattern.front());
+  EXPECT_EQ(SPV_OPERAND_TYPE_NONE, pattern.back());
 }
 
-TEST(OperandPattern, PopFrontsAreOnTheLeft) {
-  spv_operand_pattern_t pattern{SPV_OPERAND_TYPE_LITERAL_INTEGER,
-                                SPV_OPERAND_TYPE_ID};
+TEST(OperandPattern, PopBacksAreOnTheRight) {
+  spv_operand_pattern_t pattern{SPV_OPERAND_TYPE_ID,
+                                SPV_OPERAND_TYPE_LITERAL_INTEGER};
 
-  pattern.pop_front();
+  pattern.pop_back();
   EXPECT_THAT(pattern, Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_ID}));
 
-  pattern.pop_front();
+  pattern.pop_back();
   EXPECT_THAT(pattern, Eq(spv_operand_pattern_t{}));
 }
 
@@ -72,44 +72,44 @@ TEST_P(MaskExpansionTest, Sample) {
             spvOperandTableGet(&operandTable, SPV_ENV_UNIVERSAL_1_0));
 
   spv_operand_pattern_t pattern(GetParam().initial);
-  spvPrependOperandTypesForMask(operandTable, GetParam().type, GetParam().mask,
+  spvPushOperandTypesForMask(operandTable, GetParam().type, GetParam().mask,
                                 &pattern);
   EXPECT_THAT(pattern, Eq(GetParam().expected));
 }
 
 // These macros let us write non-trivial examples without too much text.
-#define SUFFIX0 SPV_OPERAND_TYPE_NONE, SPV_OPERAND_TYPE_ID
-#define SUFFIX1                                              \
-  SPV_OPERAND_TYPE_ID, SPV_OPERAND_TYPE_SAMPLER_FILTER_MODE, \
-      SPV_OPERAND_TYPE_STORAGE_CLASS
+#define PREFIX0 SPV_OPERAND_TYPE_ID, SPV_OPERAND_TYPE_NONE
+#define PREFIX1                                              \
+  SPV_OPERAND_TYPE_STORAGE_CLASS, SPV_OPERAND_TYPE_SAMPLER_FILTER_MODE, \
+      SPV_OPERAND_TYPE_ID
 INSTANTIATE_TEST_CASE_P(
     OperandPattern, MaskExpansionTest,
     ::testing::ValuesIn(std::vector<MaskExpansionCase>{
         // No bits means no change.
-        {SPV_OPERAND_TYPE_OPTIONAL_MEMORY_ACCESS, 0, {SUFFIX0}, {SUFFIX0}},
+        {SPV_OPERAND_TYPE_OPTIONAL_MEMORY_ACCESS, 0, {PREFIX0}, {PREFIX0}},
         // Unknown bits means no change.
         {SPV_OPERAND_TYPE_OPTIONAL_MEMORY_ACCESS,
          0xfffffffc,
-         {SUFFIX1},
-         {SUFFIX1}},
+         {PREFIX1},
+         {PREFIX1}},
         // Volatile has no operands.
         {SPV_OPERAND_TYPE_OPTIONAL_MEMORY_ACCESS,
          SpvMemoryAccessVolatileMask,
-         {SUFFIX0},
-         {SUFFIX0}},
+         {PREFIX0},
+         {PREFIX0}},
         // Aligned has one literal number operand.
         {SPV_OPERAND_TYPE_OPTIONAL_MEMORY_ACCESS,
          SpvMemoryAccessAlignedMask,
-         {SUFFIX1},
-         {SPV_OPERAND_TYPE_LITERAL_INTEGER, SUFFIX1}},
+         {PREFIX1},
+         {PREFIX1, SPV_OPERAND_TYPE_LITERAL_INTEGER}},
         // Volatile with Aligned still has just one literal number operand.
         {SPV_OPERAND_TYPE_OPTIONAL_MEMORY_ACCESS,
          SpvMemoryAccessVolatileMask | SpvMemoryAccessAlignedMask,
-         {SUFFIX1},
-         {SPV_OPERAND_TYPE_LITERAL_INTEGER, SUFFIX1}},
+         {PREFIX1},
+         {PREFIX1, SPV_OPERAND_TYPE_LITERAL_INTEGER}},
     }), );
-#undef SUFFIX0
-#undef SUFFIX1
+#undef PREFIX0
+#undef PREFIX1
 
 // Returns a vector of all operand types that can be used in a pattern.
 std::vector<spv_operand_type_t> allOperandTypes() {
@@ -149,7 +149,7 @@ TEST_P(VariableOperandExpansionTest, NonMatchableOperandsExpand) {
     EXPECT_FALSE(pattern.empty());
     // For the existing rules, the first expansion of a zero-or-more operand
     // type yields a matchable operand type.  This isn't strictly necessary.
-    EXPECT_FALSE(spvOperandIsVariable(pattern.front()));
+    EXPECT_FALSE(spvOperandIsVariable(pattern.back()));
   }
 }
 
@@ -183,8 +183,8 @@ TEST(AlternatePatternFollowingImmediate, SingleElement) {
 TEST(AlternatePatternFollowingImmediate, SingleResultId) {
   EXPECT_THAT(
       spvAlternatePatternFollowingImmediate({SPV_OPERAND_TYPE_RESULT_ID}),
-      Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_RESULT_ID,
-                               SPV_OPERAND_TYPE_OPTIONAL_CIV}));
+      Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_OPTIONAL_CIV,
+                               SPV_OPERAND_TYPE_RESULT_ID}));
 }
 
 TEST(AlternatePatternFollowingImmediate, MultipleNonResultIds) {
@@ -199,12 +199,15 @@ TEST(AlternatePatternFollowingImmediate, MultipleNonResultIds) {
 TEST(AlternatePatternFollowingImmediate, ResultIdFront) {
   EXPECT_THAT(spvAlternatePatternFollowingImmediate(
                   {SPV_OPERAND_TYPE_RESULT_ID, SPV_OPERAND_TYPE_ID}),
-              Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_RESULT_ID,
+              Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_OPTIONAL_CIV,
+                                       SPV_OPERAND_TYPE_RESULT_ID,
                                        SPV_OPERAND_TYPE_OPTIONAL_CIV}));
   EXPECT_THAT(spvAlternatePatternFollowingImmediate(
                   {SPV_OPERAND_TYPE_RESULT_ID,
                    SPV_OPERAND_TYPE_FP_ROUNDING_MODE, SPV_OPERAND_TYPE_ID}),
-              Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_RESULT_ID,
+              Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_OPTIONAL_CIV,
+                                       SPV_OPERAND_TYPE_RESULT_ID,
+                                       SPV_OPERAND_TYPE_OPTIONAL_CIV,
                                        SPV_OPERAND_TYPE_OPTIONAL_CIV}));
   EXPECT_THAT(spvAlternatePatternFollowingImmediate(
                   {SPV_OPERAND_TYPE_RESULT_ID, SPV_OPERAND_TYPE_DIMENSIONALITY,
@@ -212,7 +215,13 @@ TEST(AlternatePatternFollowingImmediate, ResultIdFront) {
                    SPV_OPERAND_TYPE_FUNCTION_PARAMETER_ATTRIBUTE,
                    SPV_OPERAND_TYPE_FP_ROUNDING_MODE, SPV_OPERAND_TYPE_ID,
                    SPV_OPERAND_TYPE_VARIABLE_ID}),
-              Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_RESULT_ID,
+              Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_OPTIONAL_CIV,
+                                       SPV_OPERAND_TYPE_RESULT_ID,
+                                       SPV_OPERAND_TYPE_OPTIONAL_CIV,
+                                       SPV_OPERAND_TYPE_OPTIONAL_CIV,
+                                       SPV_OPERAND_TYPE_OPTIONAL_CIV,
+                                       SPV_OPERAND_TYPE_OPTIONAL_CIV,
+                                       SPV_OPERAND_TYPE_OPTIONAL_CIV,
                                        SPV_OPERAND_TYPE_OPTIONAL_CIV}));
 }
 
@@ -230,8 +239,8 @@ TEST(AlternatePatternFollowingImmediate, ResultIdMiddle) {
            SPV_OPERAND_TYPE_RESULT_ID, SPV_OPERAND_TYPE_FP_ROUNDING_MODE,
            SPV_OPERAND_TYPE_ID, SPV_OPERAND_TYPE_VARIABLE_ID}),
       Eq(spv_operand_pattern_t{
-          SPV_OPERAND_TYPE_OPTIONAL_CIV, SPV_OPERAND_TYPE_OPTIONAL_CIV,
           SPV_OPERAND_TYPE_OPTIONAL_CIV, SPV_OPERAND_TYPE_RESULT_ID,
+          SPV_OPERAND_TYPE_OPTIONAL_CIV, SPV_OPERAND_TYPE_OPTIONAL_CIV,
           SPV_OPERAND_TYPE_OPTIONAL_CIV}));
 }
 
@@ -239,14 +248,12 @@ TEST(AlternatePatternFollowingImmediate, ResultIdBack) {
   EXPECT_THAT(spvAlternatePatternFollowingImmediate(
                   {SPV_OPERAND_TYPE_ID, SPV_OPERAND_TYPE_RESULT_ID}),
               Eq(spv_operand_pattern_t{SPV_OPERAND_TYPE_OPTIONAL_CIV,
-                                       SPV_OPERAND_TYPE_RESULT_ID,
-                                       SPV_OPERAND_TYPE_OPTIONAL_CIV}));
+                                       SPV_OPERAND_TYPE_RESULT_ID}));
   EXPECT_THAT(spvAlternatePatternFollowingImmediate(
                   {SPV_OPERAND_TYPE_FP_ROUNDING_MODE, SPV_OPERAND_TYPE_ID,
                    SPV_OPERAND_TYPE_RESULT_ID}),
               Eq(spv_operand_pattern_t{
-                  SPV_OPERAND_TYPE_OPTIONAL_CIV, SPV_OPERAND_TYPE_OPTIONAL_CIV,
-                  SPV_OPERAND_TYPE_RESULT_ID, SPV_OPERAND_TYPE_OPTIONAL_CIV}));
+                  SPV_OPERAND_TYPE_OPTIONAL_CIV, SPV_OPERAND_TYPE_RESULT_ID}));
   EXPECT_THAT(
       spvAlternatePatternFollowingImmediate(
           {SPV_OPERAND_TYPE_DIMENSIONALITY, SPV_OPERAND_TYPE_LINKAGE_TYPE,
@@ -254,10 +261,7 @@ TEST(AlternatePatternFollowingImmediate, ResultIdBack) {
            SPV_OPERAND_TYPE_FP_ROUNDING_MODE, SPV_OPERAND_TYPE_ID,
            SPV_OPERAND_TYPE_VARIABLE_ID, SPV_OPERAND_TYPE_RESULT_ID}),
       Eq(spv_operand_pattern_t{
-          SPV_OPERAND_TYPE_OPTIONAL_CIV, SPV_OPERAND_TYPE_OPTIONAL_CIV,
-          SPV_OPERAND_TYPE_OPTIONAL_CIV, SPV_OPERAND_TYPE_OPTIONAL_CIV,
-          SPV_OPERAND_TYPE_OPTIONAL_CIV, SPV_OPERAND_TYPE_OPTIONAL_CIV,
-          SPV_OPERAND_TYPE_RESULT_ID, SPV_OPERAND_TYPE_OPTIONAL_CIV}));
+          SPV_OPERAND_TYPE_OPTIONAL_CIV, SPV_OPERAND_TYPE_RESULT_ID}));
 }
 
 }  // anonymous namespace