Add basic support for SPV_KHR_shader_ballot

Requires use of SPIRV-Headers that has support
for SPV_KHR_shader_ballot.

Adds assembler, disassembler, binary parser support.

Adds general support for allowing an operand to be
only enabled by a set of extensions.

TODO: Validator support for extension checking.
diff --git a/CHANGES b/CHANGES
index cd295e1..1a307b1 100644
--- a/CHANGES
+++ b/CHANGES
@@ -1,6 +1,7 @@
 Revision history for SPIRV-Tools
 
-v2016.5-dev 2016-09-12
+v2016.5-dev 2016-09-16
+ - Support SPV_KHR_shader_ballot in assembler, disassembler, parser.
  - Disassembler: Generate friendly names for built-in variables.
  - Partial fixes:
    #359: Add Emacs helper for automatically diassembling/assembling a SPIR-V
diff --git a/source/table.h b/source/table.h
index abce443..a1f5277 100644
--- a/source/table.h
+++ b/source/table.h
@@ -21,6 +21,18 @@
 #include "message.h"
 #include "spirv-tools/libspirv.h"
 
+namespace libspirv {
+
+// The known SPIR-V extensions.
+// TODO(dneto): Consider auto-generating this list?
+enum class Extension {
+  kSPV_KHR_shader_ballot
+};
+
+using ExtensionSet = EnumSet<Extension>;
+
+} // namespace libspirv
+
 typedef struct spv_opcode_desc_t {
   const char* name;
   const SpvOp opcode;
@@ -38,6 +50,12 @@
   const char* name;
   const uint32_t value;
   const libspirv::CapabilitySet capabilities;
+  // A set of extensions that enable this feature. If empty then this operand
+  // value is always enabled, i.e. it's in core.  The assembler, binary parser,
+  // and disassembler ignore this rule, so you can freely process invalid
+  // modules.
+  // TODO(dneto): Add validator support to check extensions.
+  const libspirv::ExtensionSet extensions;
   const spv_operand_type_t operandTypes[16];  // TODO: Smaller/larger?
 } spv_operand_desc_t;
 
diff --git a/test/TextToBinary.Extension.cpp b/test/TextToBinary.Extension.cpp
index 9dc0be6..8c78f5d 100644
--- a/test/TextToBinary.Extension.cpp
+++ b/test/TextToBinary.Extension.cpp
@@ -28,7 +28,10 @@
 using spvtest::MakeInstruction;
 using spvtest::MakeVector;
 using spvtest::TextToBinaryTest;
+using ::testing::Combine;
 using ::testing::Eq;
+using ::testing::Values;
+using ::testing::ValuesIn;
 
 TEST_F(TextToBinaryTest, InvalidExtInstImportName) {
   EXPECT_THAT(CompileFailure("%1 = OpExtInstImport \"Haskell.std\""),
@@ -86,4 +89,60 @@
   EXPECT_THAT(EncodeAndDecodeSuccessfully(input), Eq(input));
 }
 
+
+// SPV_KHR_shader_ballot
+
+// A test case for assembling into words in an instruction.
+struct AssemblyCase {
+  std::string input;
+  std::vector<uint32_t> expected;
+};
+
+using SPV_KHR_shader_ballot_Test = spvtest::TextToBinaryTestBase<
+    ::testing::TestWithParam<std::tuple<spv_target_env, AssemblyCase>>>;
+
+TEST_P(SPV_KHR_shader_ballot_Test, Samples) {
+  const spv_target_env& env = std::get<0>(GetParam());
+  const AssemblyCase& ac = std::get<1>(GetParam());
+
+  // Check that it assembles correctly.
+  EXPECT_THAT(CompiledInstructions(ac.input, env), Eq(ac.expected));
+
+  // Check round trip through the disassembler.
+  EXPECT_THAT(EncodeAndDecodeSuccessfully(ac.input,
+                                          SPV_BINARY_TO_TEXT_OPTION_NONE, env),
+              Eq(ac.input));
+}
+
+INSTANTIATE_TEST_CASE_P(
+    Assembly, SPV_KHR_shader_ballot_Test,
+    // We'll get coverage over operand tables by trying the universal
+    // environments, and at least one specific environment.
+    Combine(Values(SPV_ENV_UNIVERSAL_1_0, SPV_ENV_UNIVERSAL_1_1,
+                   SPV_ENV_VULKAN_1_0),
+            ValuesIn(std::vector<AssemblyCase>{
+                {"OpCapability SubgroupBallotKHR\n",
+                 MakeInstruction(SpvOpCapability,
+                                 {SpvCapabilitySubgroupBallotKHR})},
+                {"%2 = OpSubgroupBallotKHR %1 %3\n",
+                 MakeInstruction(SpvOpSubgroupBallotKHR, {1, 2, 3})},
+                {"%2 = OpSubgroupFirstInvocationKHR %1 %3\n",
+                 MakeInstruction(SpvOpSubgroupFirstInvocationKHR, {1, 2, 3})},
+                {"OpDecorate %1 BuiltIn SubgroupEqMaskKHR\n",
+                 MakeInstruction(SpvOpDecorate, {1, SpvDecorationBuiltIn,
+                                                 SpvBuiltInSubgroupEqMaskKHR})},
+                {"OpDecorate %1 BuiltIn SubgroupGeMaskKHR\n",
+                 MakeInstruction(SpvOpDecorate, {1, SpvDecorationBuiltIn,
+                                                 SpvBuiltInSubgroupGeMaskKHR})},
+                {"OpDecorate %1 BuiltIn SubgroupGtMaskKHR\n",
+                 MakeInstruction(SpvOpDecorate, {1, SpvDecorationBuiltIn,
+                                                 SpvBuiltInSubgroupGtMaskKHR})},
+                {"OpDecorate %1 BuiltIn SubgroupLeMaskKHR\n",
+                 MakeInstruction(SpvOpDecorate, {1, SpvDecorationBuiltIn,
+                                                 SpvBuiltInSubgroupLeMaskKHR})},
+                {"OpDecorate %1 BuiltIn SubgroupLtMaskKHR\n",
+                 MakeInstruction(SpvOpDecorate, {1, SpvDecorationBuiltIn,
+                                                 SpvBuiltInSubgroupLtMaskKHR})},
+            })), );
+
 }  // anonymous namespace
diff --git a/utils/generate_grammar_tables.py b/utils/generate_grammar_tables.py
index f05a15a..4c1da59 100755
--- a/utils/generate_grammar_tables.py
+++ b/utils/generate_grammar_tables.py
@@ -53,6 +53,18 @@
     return "{" + ", ".join(['SpvCapability{}'.format(c) for c in caps]) + "}"
 
 
+def compose_extension_list(exts):
+    """Returns a string containing a braced list of extensions as enums.
+
+    Arguments:
+      - exts: a sequence of extension names
+
+    Returns:
+      a string containing the braced list of SpvCapability* enums named by caps.
+    """
+    return "{" + ", ".join(['libspirv::Extension::k{}'.format(e) for e in exts]) + "}"
+
+
 def convert_operand_kind(operand_tuple):
     """Returns the corresponding operand type used in spirv-tools for
     the given operand kind and quantifier used in the JSON grammar.
@@ -236,27 +248,30 @@
 class EnumerantInitializer(object):
     """Prints an enumerant as the initializer for spv_operand_desc_t."""
 
-    def __init__(self, enumerant, value, caps, parameters):
+    def __init__(self, enumerant, value, caps, exts, parameters):
         """Initialization.
 
         Arguments:
           - enumerant: enumerant name
           - value: enumerant value
           - caps: a sequence of capability names required by this enumerant
+          - exts: a sequence of names of extensions enabling this enumerant
           - parameters: a sequence of (operand-kind, operand-quantifier) tuples
         """
         self.enumerant = enumerant
         self.value = value
-        self.caps_mask = compose_capability_list(caps)
+        self.caps = compose_capability_list(caps)
+        self.exts = compose_extension_list(exts)
         self.parameters = [convert_operand_kind(p) for p in parameters]
 
     def __str__(self):
         template = ['{{"{enumerant}"', '{value}',
-                    '{caps_mask}', '{{{parameters}}}}}']
+                    '{caps}', '{exts}', '{{{parameters}}}}}']
         return ', '.join(template).format(
             enumerant=self.enumerant,
             value=self.value,
-            caps_mask=self.caps_mask,
+            caps=self.caps,
+            exts=self.exts,
             parameters=', '.join(self.parameters))
 
 
@@ -272,6 +287,7 @@
     enumerant = entry.get('enumerant')
     value = entry.get('value')
     caps = entry.get('capabilities', [])
+    exts = entry.get('exts', [])
     params = entry.get('parameters', [])
     params = [p.get('kind') for p in params]
     params = zip(params, [''] * len(params))
@@ -279,7 +295,7 @@
     assert enumerant is not None
     assert value is not None
 
-    return str(EnumerantInitializer(enumerant, value, caps, params))
+    return str(EnumerantInitializer(enumerant, value, caps, exts, params))
 
 
 def generate_enum_operand_kind(enum):