Unexpected Null Character Sorting in Tcl SQLite Due to Modified UTF-8 Encoding

Issue Overview: Null Characters Sorted Incorrectly in Tcl SQLite Queries

The core issue revolves around unexpected sorting behavior when inserting and retrieving text values containing the null character (\x00) via SQLite’s Tcl interface. A minimal Tcl script demonstrates the problem: inserting the hexadecimal values \x00, \x7f, and \x80 into a SQLite database and sorting them using the BINARY collation produces 127 0 128 instead of the expected 0 127 128. This discrepancy arises due to how Tcl internally encodes strings and interacts with SQLite’s text storage.

Key Observations:

1. Data Encoding Discrepancy:
   The null character (\x00) is encoded by Tcl as a two-byte sequence (0xC0 0x80) instead of the standard single-byte 0x00. This is a feature of Tcl’s internal string representation, which uses Modified UTF-8 to avoid conflicts with null-terminated strings in C-based APIs.

2. Collation Behavior:
   SQLite’s BINARY collation sorts text values lexicographically based on their raw byte sequences. The two-byte encoding of \x00 (0xC0 0x80) places it between \x7f (encoded as 0x7f) and \x80 (encoded as 0xC2 0x80 in standard UTF-8 for Unicode code points above U+007F).

3. Cross-Language Compatibility:
   The issue becomes critical when databases created via the Tcl interface are accessed by other programming languages or tools that expect standard UTF-8 encoding. The overlong encoding of \x00 breaks assumptions about valid UTF-8 and causes sorting/comparison mismatches.

Technical Context:

• Modified UTF-8:
  Tcl uses a variant of UTF-8 that encodes \x00 as 0xC0 0x80 to allow null characters in strings without conflicting with C-style null terminators. This is a deliberate design choice but violates the UTF-8 standard’s requirement for minimal encoding.
• SQLite’s Text Handling:
  SQLite treats text columns as sequences of bytes with no validation of UTF-8 conformance. The Tcl interface passes strings directly to SQLite without converting them to standard UTF-8, leading to unintended storage of Modified UTF-8 sequences.

Possible Causes: Tcl’s Modified UTF-8 and SQLite Collation Mismatch

1. Tcl’s Internal String Representation

Tcl represents strings internally using Modified UTF-8, which allows embedded null characters. When binding parameters via db eval, the Tcl interface passes these raw bytes to SQLite. For example:

db eval { INSERT INTO t VALUES ($val) }  

Here, $val is passed as a Tcl string object, which may include Modified UTF-8 sequences. SQLite stores these bytes verbatim, unaware of their non-standard encoding.

2. SQLite’s Collation Rules

The BINARY collation sorts text by comparing byte values directly. The two-byte encoding of \x00 (0xC0 0x80) has a higher byte value than 0x7f but lower than 0x80 (when interpreted as unsigned integers). This results in the order \x7f (127), \x00 (misinterpreted as 0xC0 0x80), then \x80 (128).

3. Binding Layer Omission

The SQLite Tcl interface (tclsqlite.c) does not convert strings to standard UTF-8 before binding them to SQL parameters. Unlike other language bindings (e.g., Python or Java), it assumes the application handles encoding/decoding, which is incorrect for Tcl due to its Modified UTF-8 usage.

4. Overlong Encoding Ambiguity

The Modified UTF-8 sequence 0xC0 0x80 is an overlong encoding of \x00, which is disallowed by the Unicode Standard. Systems expecting valid UTF-8 may reject or mishandle such sequences, leading to data corruption or security issues.

Troubleshooting Steps, Solutions & Fixes

Step 1: Validate Encoding in the Database

Use SQLite’s quote() and CAST functions to inspect stored values:

puts [db eval { SELECT rowid, quote(CAST(v AS BLOB)) FROM t }]  

This reveals whether values are stored as Modified UTF-8 (e.g., X'C080' for \x00) or standard UTF-8.

Step 2: Modify the Tcl Interface to Use Standard UTF-8

Fix the Binding Layer:
Modify tclsqlite.c to convert Tcl strings to standard UTF-8 before passing them to SQLite. Use Tcl_UtfToExternalDString with UTF-8 encoding:

Tcl_DString ds;  
const char *utf8 = Tcl_UtfToExternalDString(NULL, Tcl_GetString(obj), -1, &ds);  
// Bind utf8 to SQL parameter  
Tcl_DStringFree(&ds);  

This ensures \x00 is stored as 0x00 instead of 0xC0 0x80.

Backward Compatibility:
Introduce a new Tcl command (e.g., sqlite3_use_standard_utf8) to toggle encoding behavior. Legacy applications relying on Modified UTF-8 can opt out.

Step 3: Custom Collation for Modified UTF-8

If modifying the Tcl interface is impractical, define a custom collation that decodes Modified UTF-8 before comparison:

db collate modified_utf8 {a b} {  
    # Decode a and b from Modified UTF-8, then compare as integers  
}  

Use this collation in queries:

SELECT v FROM t ORDER BY v COLLATE modified_utf8;  

Step 4: Data Migration for Existing Databases

For databases containing Modified UTF-8 values, migrate affected columns:

1. Detect Non-Standard Values:

   SELECT rowid, v FROM t WHERE v LIKE '%\xC0\x80%';  
   

2. Update to Standard UTF-8:

   UPDATE t SET v = REPLACE(v, CAST('\xC0\x80' AS BLOB), CAST('\x00' AS BLOB));  
   

Step 5: Enforcement of Valid UTF-8

Add a CHECK constraint to prevent invalid UTF-8:

CREATE TABLE t (
    v TEXT CHECK (v IS NULL OR valid_utf8(v))
);  

Implement valid_utf8 as a user-defined function that rejects overlong encodings.

Step 6: Use BLOB for Non-UTF-8 Data

If storing Modified UTF-8 is unavoidable, use BLOB columns:

INSERT INTO t VALUES (CAST($val AS BLOB));  

This preserves byte sequences without implicating collation rules.

Step 7: Update Documentation and Best Practices

• Tcl Interface:
  Clearly document that strings are stored as Modified UTF-8 unless converted explicitly.
• Cross-Platform Warnings:
  Advise against mixing Tcl with other interfaces unless encoding consistency is enforced.

Conclusion

The root cause of the sorting anomaly lies in Tcl’s use of Modified UTF-8 and SQLite’s unopinionated text handling. Fixes involve either adapting the Tcl binding to enforce standard UTF-8 or adjusting collation/data types to account for the encoding mismatch. Proactive measures like data validation and migration ensure long-term consistency across applications.