{"record":{"id":"fbca9aad1fab3994","repo":"dotnet/machinelearning","slug":"failed-to-insert-key-wrong-key-order","errorCode":null,"errorMessage":"failed to insert key: wrong key order","messagePattern":"failed to insert key: wrong key order","errorType":"exception","errorClass":"InvalidOperationException","httpStatus":null,"severity":"error","filePath":"src/Microsoft.ML.Tokenizers/Utils/DoubleArrayTrie.cs","lineNumber":369,"sourceCode":"\n            for (; keyPos <= length; ++keyPos)\n            {\n                uint childId = _nodes[(int)id].Child;\n                if (childId == 0)\n                {\n                    break;\n                }\n\n                byte keyLabel = key[keyPos];\n                if (keyPos < length && keyLabel == 0)\n                {\n                    throw new InvalidOperationException(\"failed to insert key: invalid null character\");\n                }\n\n                byte unitLabel = _nodes[(int)childId].Label;\n                if (keyLabel < unitLabel)\n                {\n                    throw new InvalidOperationException(\"failed to insert key: wrong key order\");\n                }\n                else if (keyLabel > unitLabel)\n                {\n                    _nodes[(int)childId].HasSibling = true;\n                    Flush(childId);\n                    break;\n                }\n\n                id = childId;\n            }\n\n            if (keyPos > length)\n            {\n                return;\n            }\n\n            for (; keyPos <= length; ++keyPos)\n            {","sourceCodeStart":351,"sourceCodeEnd":387,"githubUrl":"https://github.com/dotnet/machinelearning/blob/7b76e69cf964daeca3f1377af6bc5543284d56c6/src/Microsoft.ML.Tokenizers/Utils/DoubleArrayTrie.cs#L351-L387","documentation":"Insert walks the trie in sorted key order; when it finds the current key's byte label is smaller than the existing sibling label at the current node, it throws this InvalidOperationException. The double-array build algorithm requires keys to be inserted in ascending byte order so it can flush completed nodes. Out-of-order insertion breaks the structure invariants, so it fails fast.","triggerScenarios":"Calling Insert with keys not sorted in ascending byte order, e.g. BuildDawg iterating a Dictionary<string,...> whose enumeration order is arbitrary, or inserting keys after a prior duplicate key already completed the path.","commonSituations":"Building a trie from a HashSet/Dictionary instead of a sorted collection, adding a duplicate key (equal prefix then shorter key after longer one is fine, but out-of-order distinct keys are not), or merging multiple unsorted vocab sources.","solutions":["Sort keys by their UTF-8 byte representation before inserting them all (Ordinal string sort matches byte order for UTF-8).","Collect vocabulary entries into a List and sort with StringComparer.Ordinal before the Insert loop.","Ensure each key is inserted exactly once — deduplicate before building.","Verify no code inserts into an already-built trie; DoubleArrayTrie is a build-once structure."],"exampleFix":"// before\nforeach (var kv in vocabMap)\n    trie.Insert(bytes(kv.Key), len(kv.Key), kv.Value);\n// after\nforeach (var kv in vocabMap.OrderBy(k => k.Key, StringComparer.Ordinal))\n    trie.Insert(bytes(kv.Key), len(kv.Key), kv.Value);","handlingStrategy":"validation","validationCode":"var sorted = keys.OrderBy(k => k, StringComparer.Ordinal).ToList();\nforeach (var k in sorted) trie.Insert(Encoding.UTF8.GetBytes(k), Encoding.UTF8.GetByteCount(k), id++);","typeGuard":"static bool KeysAreOrdinalSorted(IEnumerable<string> keys) => keys.SequenceEqual(keys.OrderBy(k => k, StringComparer.Ordinal));","tryCatchPattern":"try { trie.Insert(key, len, value); }\ncatch (InvalidOperationException ex) when (ex.Message.Contains(\"wrong key order\"))\n{ throw new InvalidOperationException(\"Keys must be inserted in ascending ordinal order\", ex); }","preventionTips":["Always sort keys with StringComparer.Ordinal before trie build","Never insert into a built DoubleArrayTrie — build once from a sorted list","Deduplicate keys before insertion"],"tags":["trie","ordering","sorted-insert","tokenizer"],"backgroundTag":"invalid-state-transition","analyzedSha":"7b76e69cf964daeca3f1377af6bc5543284d56c6","analyzedAt":"2026-09-11T12:35:38.930Z","contentChangedAt":"2026-09-11T12:35:38.930Z","schemaVersion":2},"datasetVersion":"2026-09-14T05:17:10.506Z"}