Merge branch 'incoming'

10 files changed, 144 insertions, 45 deletions

diff --git a/src/intertyper.js b/src/intertyper.js
index 8e7bb418..7db1a2fe 100644
--- a/src/intertyper.js
+++ b/src/intertyper.js
@@ -73,13 +73,11 @@ function intertyper(data, sidePass, baseLineNums) {
           if (!testType) {
             var global = /([@%\w\d\.\" $-]+) = .*/.exec(line);
             var globalIdent = toNiceIdent(global[1]);
-            var testAlias = /[@%\w\d\.\" $-]+ = alias .*/.exec(line);
-            var testString = /[@%\w\d\.\" $-]+ = [\w ]+ \[\d+ x i8] c".*/.exec(line);
+            var testAlias = /[@%\w\d\.\" $-]+ = (hidden )?alias .*/.exec(line);
             Variables.globals[globalIdent] = {
               name: globalIdent,
               alias: !!testAlias,
-              impl: VAR_EMULATED,
-              isString : !!testString
+              impl: VAR_EMULATED
             };
             unparsedGlobals.lines.push(line);
           } else {
@@ -459,6 +457,9 @@ function intertyper(data, sidePass, baseLineNums) {
         };
         ret.type = ret.value.type;
         Types.needAnalysis[ret.type] = 0;
+        if (!NAMED_GLOBALS) {
+          Variables.globals[ret.ident].type = ret.type;
+        }
         return [ret];
       }
       if (item.tokens[2].text == 'type') {
@@ -509,6 +510,10 @@ function intertyper(data, sidePass, baseLineNums) {
           private_: private_,
           lineNum: item.lineNum
         };
+        if (!NAMED_GLOBALS) {
+          Variables.globals[ret.ident].type = ret.type;
+          Variables.globals[ret.ident].external = external;
+        }
         Types.needAnalysis[ret.type] = 0;
         if (ident == '@llvm.global_ctors') {
           ret.ctors = [];
diff --git a/src/jsifier.js b/src/jsifier.js
index 595e057c..ce094e1e 100644
--- a/src/jsifier.js
+++ b/src/jsifier.js
@@ -217,7 +217,7 @@ function JSify(data, functionsOnly, givenFunctions) {
           throw 'Invalid segment: ' + dump(segment);
         }
         assert(segment.type, 'Missing type for constant segment!');
-        return indexizeFunctions(ret, segment.type);
+        return makeGlobalUse(indexizeFunctions(ret, segment.type));
       };
       return tokens.map(handleSegment)
     }
@@ -226,7 +226,7 @@ function JSify(data, functionsOnly, givenFunctions) {
     if (value.intertype in PARSABLE_LLVM_FUNCTIONS) {
       return [finalizeLLVMFunctionCall(value)];
     } else if (Runtime.isNumberType(type) || pointingLevels(type) >= 1) {
-      return indexizeFunctions(parseNumerical(value.value), type);
+      return makeGlobalUse(indexizeFunctions(parseNumerical(value.value), type));
     } else if (value.intertype === 'emptystruct') {
       return makeEmptyStruct(type);
     } else if (value.intertype === 'string') {
@@ -250,7 +250,7 @@ function JSify(data, functionsOnly, givenFunctions) {
     processItem: function(item) {
       function needsPostSet(value) {
         return value[0] in UNDERSCORE_OPENPARENS || value.substr(0, 14) === 'CHECK_OVERFLOW'
-            || value.substr(0, 13) === 'STRING_TABLE.';
+                                                 || value.substr(0, 6) === 'GLOBAL';
       }
 
       item.intertype = 'GlobalVariableStub';
@@ -262,16 +262,17 @@ function JSify(data, functionsOnly, givenFunctions) {
                   '\n]);\n';
         return ret;
       } else {
+        var constant = null;
+        var allocator = (BUILD_AS_SHARED_LIB && !item.external) ? 'ALLOC_NORMAL' : 'ALLOC_STATIC';
+        var index = null;
         if (item.external && BUILD_AS_SHARED_LIB) {
           // External variables in shared libraries should not be declared as
           // they would shadow similarly-named globals in the parent.
           item.JS = '';
         } else {
-          if (!(item.ident in Variables.globals) || !Variables.globals[item.ident].isString) {
-          	item.JS = 'var ' + item.ident + ';';
-          } 
+        	item.JS = makeGlobalDef(item.ident);
         }
-        var constant = null;
+
         if (item.external) {
           // Import external global variables from the library if available.
           var shortident = item.ident.slice(1);
@@ -286,7 +287,7 @@ function JSify(data, functionsOnly, givenFunctions) {
               padding = makeEmptyStruct(item.type);
             }
             var padded = val.concat(padding.slice(val.length));
-            var js = item.ident + '=' + makePointer(JSON.stringify(padded), null, 'ALLOC_STATIC', item.type) + ';'
+            var js = item.ident + '=' + makePointer(JSON.stringify(padded), null, allocator, item.type, index) + ';'
             if (LibraryManager.library[shortident + '__postset']) {
               js += '\n' + LibraryManager.library[shortident + '__postset'];
             }
@@ -297,6 +298,10 @@ function JSify(data, functionsOnly, givenFunctions) {
           }
           return ret;
         } else {
+          if (!NAMED_GLOBALS && isIndexableGlobal(item.ident)) {
+            index = makeGlobalUse(item.ident); // index !== null indicates we are indexing this
+            allocator = 'ALLOC_NONE';
+          }
           constant = parseConst(item.value, item.type, item.ident);
           if (typeof constant === 'string' && constant[0] != '[') {
             constant = [constant]; // A single item. We may need a postset for it.
@@ -307,7 +312,7 @@ function JSify(data, functionsOnly, givenFunctions) {
               if (needsPostSet(value)) { // ident, or expression containing an ident
                 ret.push({
                   intertype: 'GlobalVariablePostSet',
-                  JS: makeSetValue(item.ident, i, value, 'i32', false, true) + ';' // ignore=true, since e.g. rtti and statics cause lots of safe_heap errors
+                  JS: makeSetValue(makeGlobalUse(item.ident), i, value, 'i32', false, true) + ';' // ignore=true, since e.g. rtti and statics cause lots of safe_heap errors
                 });
                 constant[i] = '0';
               }
@@ -316,21 +321,17 @@ function JSify(data, functionsOnly, givenFunctions) {
           }
           // NOTE: This is the only place that could potentially create static
           //       allocations in a shared library.
-          constant = makePointer(constant, null, BUILD_AS_SHARED_LIB ? 'ALLOC_NORMAL' : 'ALLOC_STATIC', item.type);
-
+          constant = makePointer(constant, null, allocator, item.type, index);
           var js;
 
-          // Strings are held in STRING_TABLE, to not clutter up the main namespace (in some cases we have
-          // many many strings, possibly exceeding the js engine limit on global vars).
-          if (Variables.globals[item.ident].isString) {
-            js = 'STRING_TABLE.' + item.ident + '=' + constant + ';';
-          } else {
-          	js = item.ident + '=' + constant + ';';
-          }
+        	js = (index !== null ? '' : item.ident + '=') + constant + ';'; // \n Module.print("' + item.ident + ' :" + ' + makeGlobalUse(item.ident) + ');';
 
           // Special case: class vtables. We make sure they are null-terminated, to allow easy runtime operations
           if (item.ident.substr(0, 5) == '__ZTV') {
-            js += '\n' + makePointer('[0]', null, BUILD_AS_SHARED_LIB ? 'ALLOC_NORMAL' : 'ALLOC_STATIC', ['void*']) + ';';
+            if (index !== null) {
+              index = getFastValue(index, '+', Runtime.alignMemory(calcAllocatedSize(Variables.globals[item.ident].type)));
+            }
+            js += '\n' + makePointer('[0]', null, allocator, ['void*'], index) + ';';
           }
           if (EXPORT_ALL || (item.ident in EXPORTED_GLOBALS)) {
             js += '\nModule["' + item.ident + '"] = ' + item.ident + ';';
@@ -821,7 +822,7 @@ function JSify(data, functionsOnly, givenFunctions) {
         break;
       case VAR_EMULATED:
         if (item.pointer.intertype == 'value') {
-          return makeSetValue(item.ident, 0, value, item.valueType, 0, 0, item.align) + ';';
+          return makeSetValue(makeGlobalUse(item.ident), 0, value, item.valueType, 0, 0, item.align) + ';';
         } else {
           return makeSetValue(0, finalizeLLVMParameter(item.pointer), value, item.valueType, 0, 0, item.align) + ';';
         }
@@ -1278,6 +1279,15 @@ function JSify(data, functionsOnly, givenFunctions) {
     //
 
     if (!mainPass) {
+      if (phase == 'pre' && !Variables.generatedGlobalBase) {
+        Variables.generatedGlobalBase = true;
+        if (Variables.nextIndexedOffset > 0) {
+          // Variables have been calculated, print out the base generation before we print them
+          print('var GLOBAL_BASE = STATICTOP;\n');
+          print('STATICTOP += ' + Variables.nextIndexedOffset + ';\n');
+          print('assert(STATICTOP < TOTAL_MEMORY);\n');
+        }
+      }
       var generated = itemsDict.function.concat(itemsDict.type).concat(itemsDict.GlobalVariableStub).concat(itemsDict.GlobalVariable).concat(itemsDict.GlobalVariablePostSet);
       if (!DEBUG_MEMORY) print(generated.map(function(item) { return item.JS }).join('\n'));
       return;
@@ -1286,7 +1296,23 @@ function JSify(data, functionsOnly, givenFunctions) {
     // Print out global variables and postsets TODO: batching
     if (phase == 'pre') {
       legalizedI64s = false;
-      JSify(analyzer(intertyper(data.unparsedGlobalss[0].lines, true), true), true, Functions);
+
+      var globalsData = analyzer(intertyper(data.unparsedGlobalss[0].lines, true), true);
+
+      if (!NAMED_GLOBALS) {
+        sortGlobals(globalsData.globalVariables).forEach(function(g) {
+          var ident = g.ident;
+          if (!isIndexableGlobal(ident)) return;
+          Variables.indexedGlobals[ident] = Variables.nextIndexedOffset;
+          Variables.nextIndexedOffset += Runtime.alignMemory(calcAllocatedSize(Variables.globals[ident].type));
+          if (ident.substr(0, 5) == '__ZTV') { // leave room for null-terminating the vtable
+            Variables.nextIndexedOffset += Runtime.getNativeTypeSize('i32');
+          }
+        });
+      }
+
+      JSify(globalsData, true, Functions);
+      globalsData = null;
       data.unparsedGlobalss = null;
 
       var generated = itemsDict.functionStub.concat(itemsDict.GlobalVariablePostSet);
@@ -1350,7 +1376,7 @@ function JSify(data, functionsOnly, givenFunctions) {
     substrate.addItems(data.functionStubs, 'FunctionStub');
     assert(data.functions.length == 0);
   } else {
-    substrate.addItems(values(data.globalVariables), 'GlobalVariable');
+    substrate.addItems(sortGlobals(data.globalVariables), 'GlobalVariable');
     substrate.addItems(data.aliass, 'Alias');
     substrate.addItems(data.functions, 'FunctionSplitter');
   }
diff --git a/src/library.js b/src/library.js
index 12ac0ed0..5a8a9ae7 100644
--- a/src/library.js
+++ b/src/library.js
@@ -2461,6 +2461,7 @@ LibraryManager.library = {
     for (var formatIndex = 0; formatIndex < format.length;) {
       if (format[formatIndex] === '%' && format[formatIndex+1] == 'n') {
         var argPtr = {{{ makeGetValue('varargs', 'argIndex', 'void*') }}};
+        argIndex += Runtime.getNativeFieldSize('void*');
         {{{ makeSetValue('argPtr', 0, 'soFar', 'i32') }}};
         formatIndex += 2;
         continue;
@@ -3484,11 +3485,11 @@ LibraryManager.library = {
     // http://pubs.opengroup.org/onlinepubs/000095399/functions/printf.html
     var result = __formatString(format, varargs);
     var limit = (n === undefined) ? result.length
-                                  : Math.min(result.length, n - 1);
+                                  : Math.min(result.length, Math.max(n - 1, 0));
     for (var i = 0; i < limit; i++) {
       {{{ makeSetValue('s', 'i', 'result[i]', 'i8') }}};
     }
-    {{{ makeSetValue('s', 'i', '0', 'i8') }}};
+    if (limit < n || (n === undefined)) {{{ makeSetValue('s', 'i', '0', 'i8') }}};
     return result.length;
   },
   fprintf__deps: ['fwrite', '_formatString'],
@@ -3738,6 +3739,7 @@ LibraryManager.library = {
   strtod_l: 'strtod', // no locale support yet
   strtold: 'strtod', // XXX add real support for long double
   strtold_l: 'strtold', // no locale support yet
+  strtof: 'strtod', // use stdtod to handle strtof
 
   _parseInt__deps: ['isspace', '__setErrNo', '$ERRNO_CODES'],
   _parseInt: function(str, endptr, base, min, max, bits, unsign) {
@@ -5363,7 +5365,7 @@ LibraryManager.library = {
   },
   fmaxf: 'fmax',
   fmin: function(x, y) {
-    return isNaN(x) ? y : isNaN(y) ? x : Math.max(x, y);
+    return isNaN(x) ? y : isNaN(y) ? x : Math.min(x, y);
   },
   fminf: 'fmin',
   fma: function(x, y, z) {
diff --git a/src/library_gl.js b/src/library_gl.js
index 4d83572e..b4098813 100644
--- a/src/library_gl.js
+++ b/src/library_gl.js
@@ -454,8 +454,7 @@ var LibraryGL = {
   },
 
   glBufferSubData: function(target, offset, size, data) {
-    var floatArray = {{{ makeHEAPView('F32', 'data', 'data+size') }}};
-    Module.ctx.bufferSubData(target, offset, floatArray);
+    Module.ctx.bufferSubData(target, offset, HEAPU8.subarray(data, data+size));
   },
 
   glIsBuffer: function(buffer) {
diff --git a/src/modules.js b/src/modules.js
index 9ef87691..fd0ec35e 100644
--- a/src/modules.js
+++ b/src/modules.js
@@ -174,7 +174,10 @@ var PreProcessor = {
 };
 
 var Variables = {
-  globals: {}
+  globals: {},
+  indexedGlobals: {}, // for indexed globals, ident ==> index
+  // Used in calculation of indexed globals
+  nextIndexedOffset: 0
 };
 
 var Types = {
@@ -263,6 +266,7 @@ var Functions = {
 
 var LibraryManager = {
   library: null,
+  loaded: false,
 
   load: function() {
     assert(!this.library);
@@ -271,6 +275,8 @@ var LibraryManager = {
     for (var i = 0; i < libraries.length; i++) {
       eval(processMacros(preprocess(read(libraries[i]))));
     }
+
+    this.loaded = true;
   },
 
   // Given an ident, see if it is an alias for something, and so forth, returning
diff --git a/src/parseTools.js b/src/parseTools.js
index c70b511a..7387bf31 100644
--- a/src/parseTools.js
+++ b/src/parseTools.js
@@ -356,6 +356,40 @@ function hasVarArgs(params) {
   return false;
 }
 
+var UNINDEXABLE_GLOBALS = set(
+  '_llvm_global_ctors' // special-cased
+);
+
+function noticePtr(ptr) {
+  if (!NAMED_GLOBALS && !LibraryManager.loaded) UNINDEXABLE_GLOBALS[ptr] = 1; // we cannot index globals referred to in the library, since they are used there by name
+}
+
+function isIndexableGlobal(ident) {
+  if (!(ident in Variables.globals)) return false;
+  if (ident in UNINDEXABLE_GLOBALS) return false;
+  var data = Variables.globals[ident];
+  return !data.alias && !data.external;
+}
+
+function makeGlobalDef(ident) {
+  if (!NAMED_GLOBALS && isIndexableGlobal(ident)) return '';
+  return 'var ' + ident + ';'; // TODO: add option for namespacing or offsetting to allow reducing the number of globals
+}
+
+function makeGlobalUse(ident) {
+  if (!NAMED_GLOBALS && isIndexableGlobal(ident)) return '(' + getFastValue('GLOBAL_BASE', '+', Variables.indexedGlobals[ident]) + ')';
+  return ident; // TODO: add option for namespacing or offsetting to allow reducing the number of globals
+}
+
+function sortGlobals(globals) {
+  var ks = keys(globals);
+  ks.sort();
+  var inv = invertArray(ks);
+  return values(globals).sort(function(a, b) {
+    return inv[b.ident] - inv[a.ident];
+  });
+}
+
 function finalizeParam(param) {
   if (param.intertype in PARSABLE_LLVM_FUNCTIONS) {
     return finalizeLLVMFunctionCall(param);
@@ -368,10 +402,9 @@ function finalizeParam(param) {
       return parseI64Constant(param.ident);
     }
     var ret = toNiceIdent(param.ident);
-    if (ret in Variables.globals && Variables.globals[ret].isString) {
-      ret = "STRING_TABLE." + ret;
+    if (ret in Variables.globals) {
+      ret = makeGlobalUse(ret);
     }
-    
     return ret;
   }
 }
@@ -907,6 +940,7 @@ function getHeapOffset(offset, type) {
 
 // See makeSetValue
 function makeGetValue(ptr, pos, type, noNeedFirst, unsigned, ignore, align, noSafe) {
+  noticePtr(ptr);
   if (UNALIGNED_MEMORY) align = 1;
   if (isStructType(type)) {
     var typeData = Types.types[type];
@@ -987,6 +1021,7 @@ function indexizeFunctions(value, type) {
 //!             which means we should write to all slabs, ignore type differences if any on reads, etc.
 //! @param noNeedFirst Whether to ignore the offset in the pointer itself.
 function makeSetValue(ptr, pos, value, type, noNeedFirst, ignore, align, noSafe, sep, forcedAlign) {
+  noticePtr(ptr);
   if (UNALIGNED_MEMORY && !forcedAlign) align = 1;
   sep = sep || ';';
   if (isStructType(type)) {
@@ -1058,6 +1093,7 @@ var SEEK_OPTIMAL_ALIGN_MIN = 20;
 var UNROLL_LOOP_MAX = 8;
 
 function makeSetValues(ptr, pos, value, type, num, align) {
+  noticePtr(ptr);
   function unroll(type, num, jump, value$) {
     jump = jump || 1;
     value$ = value$ || value;
@@ -1107,6 +1143,8 @@ function makeSetValues(ptr, pos, value, type, num, align) {
 var TYPED_ARRAY_SET_MIN = Infinity; // .set() as memcpy seems to just slow us down
 
 function makeCopyValues(dest, src, num, type, modifier, align, sep) {
+  noticePtr(dest);
+  noticePtr(src);
   sep = sep || ';';
   function unroll(type, num, jump) {
     jump = jump || 1;
@@ -1260,7 +1298,7 @@ function makeGetPos(ptr) {
 
 var IHEAP_FHEAP = set('IHEAP', 'IHEAPU', 'FHEAP');
 
-function makePointer(slab, pos, allocator, type) {
+function makePointer(slab, pos, allocator, type, ptr) {
   assert(type, 'makePointer requires type info');
   if (slab.substr(0, 4) === 'HEAP' || (USE_TYPED_ARRAYS == 1 && slab in IHEAP_FHEAP)) return pos;
   var types = generateStructTypes(type);
@@ -1290,7 +1328,7 @@ function makePointer(slab, pos, allocator, type) {
       types = de[0];
     }
   }
-  return 'allocate(' + slab + ', ' + JSON.stringify(types) + (allocator ? ', ' + allocator : '') + ')';
+  return 'allocate(' + slab + ', ' + JSON.stringify(types) + (allocator ? ', ' + allocator : '') + (allocator == 'ALLOC_NONE' ? ', ' + ptr : '') + ')';
 }
 
 function makeGetSlabs(ptr, type, allowMultiple, unsigned) {
@@ -1472,8 +1510,8 @@ function finalizeLLVMParameter(param, noIndexizeFunctions) {
     }
   } else if (param.intertype == 'value') {
     ret = param.ident;
-    if (ret in Variables.globals && Variables.globals[ret].isString) {
-      ret = "STRING_TABLE." + ret;
+    if (ret in Variables.globals) {
+      ret = makeGlobalUse(ret);
     }
     if (param.type == 'i64' && USE_TYPED_ARRAYS == 2) {
       ret = parseI64Constant(ret);
diff --git a/src/preamble.js b/src/preamble.js
index 1c66797b..9342bf2b 100644
--- a/src/preamble.js
+++ b/src/preamble.js
@@ -472,9 +472,11 @@ Module['getValue'] = getValue;
 var ALLOC_NORMAL = 0; // Tries to use _malloc()
 var ALLOC_STACK = 1; // Lives for the duration of the current function call
 var ALLOC_STATIC = 2; // Cannot be freed
+var ALLOC_NONE = 3; // Do not allocate
 Module['ALLOC_NORMAL'] = ALLOC_NORMAL;
 Module['ALLOC_STACK'] = ALLOC_STACK;
 Module['ALLOC_STATIC'] = ALLOC_STATIC;
+Module['ALLOC_NONE'] = ALLOC_NONE;
 
 // allocate(): This is for internal use. You can use it yourself as well, but the interface
 //             is a little tricky (see docs right below). The reason is that it is optimized
@@ -489,7 +491,7 @@ Module['ALLOC_STATIC'] = ALLOC_STATIC;
 //         is initial data - if @slab is a number, then this does not matter at all and is
 //         ignored.
 // @allocator: How to allocate memory, see ALLOC_*
-function allocate(slab, types, allocator) {
+function allocate(slab, types, allocator, ptr) {
   var zeroinit, size;
   if (typeof slab === 'number') {
     zeroinit = true;
@@ -501,7 +503,12 @@ function allocate(slab, types, allocator) {
 
   var singleType = typeof types === 'string' ? types : null;
 
-  var ret = [_malloc, Runtime.stackAlloc, Runtime.staticAlloc][allocator === undefined ? ALLOC_STATIC : allocator](Math.max(size, singleType ? 1 : types.length));
+  var ret;
+  if (allocator == ALLOC_NONE) {
+    ret = ptr;
+  } else {
+    ret = [_malloc, Runtime.stackAlloc, Runtime.staticAlloc][allocator === undefined ? ALLOC_STATIC : allocator](Math.max(size, singleType ? 1 : types.length));
+  }
 
   if (zeroinit) {
       _memset(ret, 0, size);
@@ -544,6 +551,9 @@ function Pointer_stringify(ptr, /* optional */ length) {
   var i = 0;
   var t;
   while (1) {
+#if ASSERTIONS
+  assert(i < TOTAL_MEMORY);
+#endif
     t = {{{ makeGetValue('ptr', 'i', 'i8', 0, 1) }}};
     if (nullTerminated && t == 0) break;
     ret += utf8.processCChar(t);
@@ -750,7 +760,11 @@ function exitRuntime() {
 
 function String_len(ptr) {
   var i = ptr;
-  while ({{{ makeGetValue('i++', '0', 'i8') }}}) {}; // Note: should be |!= 0|, technically. But this helps catch bugs with undefineds
+  while ({{{ makeGetValue('i++', '0', 'i8') }}}) { // Note: should be |!= 0|, technically. But this helps catch bugs with undefineds
+#if ASSERTIONS
+  assert(i < TOTAL_MEMORY);
+#endif
+  }
   return i - ptr - 1;
 }
 Module['String_len'] = String_len;
@@ -806,8 +820,6 @@ function writeArrayToMemory(array, buffer) {
 }
 Module['writeArrayToMemory'] = writeArrayToMemory;
 
-var STRING_TABLE = [];
-
 {{{ unSign }}}
 {{{ reSign }}}
 
diff --git a/src/preamble_sharedlib.js b/src/preamble_sharedlib.js
index af204e2f..2a071f6b 100644
--- a/src/preamble_sharedlib.js
+++ b/src/preamble_sharedlib.js
@@ -16,7 +16,6 @@ function callRuntimeCallbacks(callbacks) {
 }
 
 var __ATINIT__ = []; // functions called during startup
-var STRING_TABLE = [];
 
 function initRuntime() {
   callRuntimeCallbacks(__ATINIT__);
diff --git a/src/settings.js b/src/settings.js
index 5dc1e2eb..1d8805a8 100644
--- a/src/settings.js
+++ b/src/settings.js
@@ -194,6 +194,10 @@ var PGO = 0; // Profile-guided optimization.
              // All CORRECT_* options default to 1 with PGO builds.
              // See https://github.com/kripken/emscripten/wiki/Optimizing-Code for more info
 
+var NAMED_GLOBALS = 1; // If 1, we use global variables for globals. Otherwise
+                       // they are referred to by a base plus an offset (called an indexed global),
+                       // saving global variables but adding runtime overhead.
+
 var PROFILE = 0; // Enables runtime profiling. See test_profiling for a usage example.
 
 var EXPORT_ALL = 0; // If true, we export all the symbols
diff --git a/src/utility.js b/src/utility.js
index f3ece90b..84b50ce9 100644
--- a/src/utility.js
+++ b/src/utility.js
@@ -282,6 +282,14 @@ function setIntersect(x, y) {
   return ret;
 }
 
+function invertArray(x) {
+  var ret = {};
+  for (var i = 0; i < x.length; i++) {
+    ret[x[i]] = i;
+  }
+  return ret;
+}
+
 function copy(x) {
   return JSON.parse(JSON.stringify(x));
 }