Skip to content

KTOR-9383 CaseInsensitiveMap and StringValuesImpl: zero-allocation header storage#5379

Merged
e5l merged 5 commits intomainfrom
e5l/opt-1-case-insensitive-map
Mar 19, 2026
Merged

KTOR-9383 CaseInsensitiveMap and StringValuesImpl: zero-allocation header storage#5379
e5l merged 5 commits intomainfrom
e5l/opt-1-case-insensitive-map

Conversation

@e5l
Copy link
Copy Markdown
Member

@e5l e5l commented Feb 24, 2026

Subsystem
ktor-utils (CaseInsensitiveMap, StringValuesImpl)

Motivation
Profiling shows CaseInsensitiveString wrapper objects are the biggest allocation hotspot in server throughput benchmarks (~2,174 samples, 1.27%), and StringValuesImpl.forEach() iterator allocations add ~300 samples. These allocations drive GC pressure under load.

Part of a series splitting e5l/opt (server throughput optimizations, ~93% GC reduction) into focused, reviewable PRs.

Solution

  • CaseInsensitiveMap: Replace MutableMap<CaseInsensitiveString, Value> delegate with an open-addressing hash table using linear probing. Case-insensitive hash and equality are computed directly on String keys — no wrapper allocations. Tracks insertion order for correct iteration (like LinkedHashMap).
  • StringValuesImpl: Replace List<Pair<String, List<String>>> with parallel arrays and a hash table with collision chaining for O(1) lookup. forEach() iterates arrays directly — zero allocation.

Eliminates ~2,474 allocation samples per profiling run.

🤖 Generated with Claude Code

@coderabbitai
Copy link
Copy Markdown
Contributor

coderabbitai Bot commented Feb 24, 2026

Note

Reviews paused

It looks like this branch is under active development. To avoid overwhelming you with review comments due to an influx of new commits, CodeRabbit has automatically paused this review. You can configure this behavior by changing the reviews.auto_review.auto_pause_after_reviewed_commits setting.

Use the following commands to manage reviews:

  • @coderabbitai resume to resume automatic reviews.
  • @coderabbitai review to trigger a single review.

Use the checkboxes below for quick actions:

  • ▶️ Resume reviews
  • 🔍 Trigger review
📝 Walkthrough

Walkthrough

Replaces delegate-based collections with custom array-backed hash-table implementations for CaseInsensitiveMap and StringValuesImpl, adds case-insensitive hashing and insertion-order/zero-allocation iteration logic, includes new tests for both classes, and applies cosmetic normalization to gradlew.bat.

Changes

Cohort / File(s) Summary
Build script
gradlew.bat
Cosmetic formatting/normalization only; no functional or control-flow changes.
Case-insensitive map implementation
ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
Rewrote internal implementation from a delegated map to an array-backed open-addressing hash table with separate key/value arrays, insertion-order tracking (IntArray), capacity management, resize/rehash, removal with cluster rehashing, custom iteration views (KeySet, ValueCollection, EntrySet), and inline case-insensitive hashing/comparisons. Public API signatures preserved.
String values storage
ktor-utils/common/src/io/ktor/util/StringValues.kt
Replaced map-backed storage with parallel arrays (keyStorage, valueStorage, entryCount) and chained hash table arrays (hashBuckets, hashNext); added computeHash/caseInsensitiveHashCode, zero-allocation iteration and lookup paths, StringValuesEntry for entry views, and a reconstructed read-only Map view for compatibility.
Tests — CaseInsensitiveMap
ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt
Added tests for insertion-order churn, case-insensitive keySet operations, and equals/hashCode behavior with differently cased keys.
Tests — StringValuesImpl
ktor-utils/common/test/io/ktor/util/StringValuesTest.kt
Added test verifying deduplication and merged values when caseInsensitiveName is true and keys differ only by case.

Estimated code review effort

🎯 4 (Complex) | ⏱️ ~45 minutes

Suggested reviewers

  • marychatte
🚥 Pre-merge checks | ✅ 2 | ❌ 1

❌ Failed checks (1 warning)

Check name Status Explanation Resolution
Docstring Coverage ⚠️ Warning Docstring coverage is 3.33% which is insufficient. The required threshold is 80.00%. Write docstrings for the functions missing them to satisfy the coverage threshold.
✅ Passed checks (2 passed)
Check name Status Explanation
Title check ✅ Passed The title accurately summarizes the main change: zero-allocation optimizations to CaseInsensitiveMap and StringValuesImpl by replacing delegation/collections with hash tables.
Description check ✅ Passed The description follows the template with Subsystem, Motivation, and Solution sections filled out comprehensively with specific performance metrics and implementation details.

✏️ Tip: You can configure your own custom pre-merge checks in the settings.

✨ Finishing Touches
🧪 Generate unit tests (beta)
  • Create PR with unit tests
  • Commit unit tests in branch e5l/opt-1-case-insensitive-map
📝 Coding Plan
  • Generate coding plan for human review comments

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

Comment @coderabbitai help to get the list of available commands and usage tips.

@e5l e5l force-pushed the e5l/opt-1-case-insensitive-map branch from 539ff09 to 322cdfc Compare February 24, 2026 11:46
Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai Bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 5

♻️ Duplicate comments (2)
ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt (2)

297-338: Same missing-message issue as above.

Please add messages for UnsupportedOperationException/IllegalStateException in this iterator as well.

As per coding guidelines, Make error messages actionable by including the problematic value and context.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt` around lines 297 -
338, The ValueCollection iterator throws bare exceptions; update
ValueCollection.add (the add(element: Value) override) to throw
UnsupportedOperationException with a clear message (e.g., "add not supported on
CaseInsensitiveMap.ValueCollection") and update the iterator.remove() path to
throw IllegalStateException with context when lastKey is null (e.g., "remove()
called before next() or after already removed for key=<lastKey?>"), and when
performing removal call this@CaseInsensitiveMap.remove(key) ensure the thrown
IllegalStateException includes the problematic key or state; reference the
ValueCollection class, its add(element: Value) method and the iterator's
remove() and lastKey variable.

340-381: Same missing-message issue as above.

Please add messages for UnsupportedOperationException/IllegalStateException in this iterator as well.

As per coding guidelines, Make error messages actionable by including the problematic value and context.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt` around lines 340 -
381, Iterator exceptions in EntrySet lack actionable messages; update the throws
to include context and problematic values: in EntrySet.add(element) replace the
plain UnsupportedOperationException with one that includes the attempted element
and that EntrySet doesn't support add (e.g., "EntrySet.add not supported:
attempted to add $element"), and in EntrySet.iterator().remove() replace the
plain IllegalStateException with one that describes the invalid remove context
and includes the lastKey when available (e.g., "remove() called without a
preceding next() on EntrySet" or "remove() called after already removed for
key=$lastKey"). Ensure you update the throw sites in the EntrySet class (add and
iterator.remove) to include these messages.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@gradlew.bat`:
- Around line 72-75: Remove the extra blank lines left between the "@rem Setup
the command line" and "@rem Execute Gradle" comment markers in gradlew.bat; open
the file, locate the two `@rem` comment lines and collapse the three consecutive
empty lines into a single blank line (or none) so the script has no stray
blank-line artifacts from removed setup commands.

In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 249-295: The KeySet inner class throws bare exceptions in add()
and iterator().remove(); update these to include actionable messages: in
KeySet.add(element: String) throw UnsupportedOperationException with a message
that includes the operation and the provided element (e.g., "add not supported
for key: <element>"); in the iterator's remove() throw IllegalStateException
with a message that indicates why removal failed and include the lastKey/state
(e.g., "remove() called before next() or after already removed;
lastKey=<value>") so logs show the problematic key and context; keep behavior
unchanged otherwise.
- Around line 168-191: Replace the current equals implementation so it accepts
any Map and compares mappings case-insensitively instead of only accepting
CaseInsensitiveMap: keep the identity check (other === this), then if other !is
Map<*,*> return false; check sizes against _size; iterate other.entries and for
each entry use the CaseInsensitiveMap key lookup (use this[entry.key as? String
?: entry.key.toString()]) to fetch the stored value and compare with entry.value
(using equals), returning false on mismatch; leave hashCode
(caseInsensitiveHashCode and valueStorage) consistent with the new equals.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt`:
- Around line 183-205: The values getter rebuilds a LinkedHashMap which loses
case-insensitive behavior; change the protected val values accessor to return a
case-insensitive map when caseInsensitiveName is true by reconstructing into the
appropriate map type instead of always using LinkedHashMap: when entryCount == 0
return emptyMap(), otherwise iterate i in 0 until entryCount and insert
keyStorage[i] -> valueStorage[i] into a caseInsensitiveMap() (or whatever
existing case-insensitive Map implementation is used) if caseInsensitiveName is
true, else use LinkedHashMap as currently implemented.

In `@ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt`:
- Around line 30-62: The tests use plain function names instead of the required
backtick-style descriptive names; rename the test functions
insertionOrderDoesNotOverflowOnChurn, keySetOperationsAreCaseInsensitive, and
equalsAndHashCodeAreCaseInsensitiveWithinMap to backtick strings (e.g.
`insertion order does not overflow on churn`, `key set operations are case
insensitive`, `equals and hashCode are case insensitive within map`) so they
follow the `describe what is being tested` pattern; ensure the `@Test` annotations
remain and update any references to these functions if present.

---

Duplicate comments:
In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 297-338: The ValueCollection iterator throws bare exceptions;
update ValueCollection.add (the add(element: Value) override) to throw
UnsupportedOperationException with a clear message (e.g., "add not supported on
CaseInsensitiveMap.ValueCollection") and update the iterator.remove() path to
throw IllegalStateException with context when lastKey is null (e.g., "remove()
called before next() or after already removed for key=<lastKey?>"), and when
performing removal call this@CaseInsensitiveMap.remove(key) ensure the thrown
IllegalStateException includes the problematic key or state; reference the
ValueCollection class, its add(element: Value) method and the iterator's
remove() and lastKey variable.
- Around line 340-381: Iterator exceptions in EntrySet lack actionable messages;
update the throws to include context and problematic values: in
EntrySet.add(element) replace the plain UnsupportedOperationException with one
that includes the attempted element and that EntrySet doesn't support add (e.g.,
"EntrySet.add not supported: attempted to add $element"), and in
EntrySet.iterator().remove() replace the plain IllegalStateException with one
that describes the invalid remove context and includes the lastKey when
available (e.g., "remove() called without a preceding next() on EntrySet" or
"remove() called after already removed for key=$lastKey"). Ensure you update the
throw sites in the EntrySet class (add and iterator.remove) to include these
messages.

ℹ️ Review info

Configuration used: Organization UI

Review profile: CHILL

Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between e94cd5e and 539ff09.

📒 Files selected for processing (4)
  • gradlew.bat
  • ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
  • ktor-utils/common/src/io/ktor/util/StringValues.kt
  • ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt

Comment thread gradlew.bat
Comment on lines +72 to +75



@rem Execute Gradle
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

⚠️ Potential issue | 🟡 Minor

Extra blank lines appear to be a formatting artifact from removed code.

Lines 72–74 leave three consecutive blank lines between @rem Setup the command line and @rem Execute Gradle. This typically indicates that intermediate setup commands (e.g., classpath-building lines present in older Gradle wrapper versions) were removed and the surrounding blank lines were not cleaned up.

🧹 Suggested cleanup
 :execute
 `@rem` Setup the command line
-
-
-
 `@rem` Execute Gradle
📝 Committable suggestion

‼️ IMPORTANT
Carefully review the code before committing. Ensure that it accurately replaces the highlighted code, contains no missing lines, and has no issues with indentation. Thoroughly test & benchmark the code to ensure it meets the requirements.

Suggested change
@rem Execute Gradle
`@rem` Setup the command line
`@rem` Execute Gradle
🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@gradlew.bat` around lines 72 - 75, Remove the extra blank lines left between
the "@rem Setup the command line" and "@rem Execute Gradle" comment markers in
gradlew.bat; open the file, locate the two `@rem` comment lines and collapse the
three consecutive empty lines into a single blank line (or none) so the script
has no stray blank-line artifacts from removed setup commands.

Comment thread ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
Comment thread ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
Comment thread ktor-utils/common/src/io/ktor/util/StringValues.kt
Comment thread ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt
Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai Bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 1

♻️ Duplicate comments (4)
gradlew.bat (1)

72-74: Three consecutive blank lines between the two @rem markers.

Lines 72–74 leave three empty lines between @rem Setup the command line and @rem Execute Gradle, which are leftover whitespace from removed setup commands.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@gradlew.bat` around lines 72 - 74, Remove the three consecutive blank lines
left between the two `@rem` markers by collapsing the whitespace so there is at
most one blank line (or none) between "@rem Setup the command line" and "@rem
Execute Gradle"; edit the gradlew.bat section containing those `@rem` comments to
delete the extra empty lines so the file has no leftover blank-line gap.
ktor-utils/common/src/io/ktor/util/StringValues.kt (1)

183-205: values getter always reconstructs a case-sensitive LinkedHashMap, even when caseInsensitiveName = true.

Subclasses that relied on case-insensitive lookups via the values map will silently regress to case-sensitive behavior. This concern was already raised for the previous implementation.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt` around lines 183 - 205,
The values getter currently reconstructs a case-sensitive LinkedHashMap
regardless of caseInsensitiveName; update the getter in StringValues (the
protected val values) to preserve case-insensitive semantics by normalizing keys
or using a case-insensitive Map when caseInsensitiveName is true (e.g., insert
keys.lowercase() or use a map implementation that compares keys ignoring case)
so subclasses that depend on case-insensitive lookups keep the same behavior;
ensure you still preserve insertion order (LinkedHashMap semantics) and return
emptyMap() when entryCount == 0.
ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt (2)

289-290: Bare exception constructors flagged by detekt at lines 290, 333, and 376 — missing actionable messages.

All three IllegalStateException() calls in the iterator remove() methods of KeySet, ValueCollection, and EntrySet lack messages. As per coding guidelines, error messages should include the problematic value and context. The static-analysis tool (detekt ThrowingExceptionsWithoutMessageOrCause) flags all three. The UnsupportedOperationException() calls in the add() overrides (lines 253, 301, 344) share the same issue.

💡 Suggested fix (pattern to apply to all three iterators)
-    val key = lastKey ?: throw IllegalStateException()
+    val key = lastKey ?: throw IllegalStateException("remove() called before next() or after already removed")
-    override fun add(element: String): Boolean =
-        throw UnsupportedOperationException()
+    override fun add(element: String): Boolean =
+        throw UnsupportedOperationException("CaseInsensitiveMap key set is read-only; add '$element' not permitted")

Also applies to: 332-333, 375-376

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt` around lines 289 -
290, Replace bare exception constructors with descriptive messages: in the
iterator remove() implementations for KeySet, ValueCollection, and EntrySet (the
methods named remove() that throw IllegalStateException()), include a clear
message that identifies the failed operation and the problematic key/value (use
lastKey/lastValue or equivalent local variable in the message). Similarly,
update the add() override methods that throw UnsupportedOperationException() to
provide a message stating the collection is immutable/unsupported and include
the attempted element (e.g., the parameter element) for context; keep using the
same exception types but pass a descriptive string to the constructor.

168-180: equals() only accepts CaseInsensitiveMap — violates the Map.equals symmetry contract.

other !is CaseInsensitiveMap<*> returns false for any regular Map, creating an asymmetry: a HashMap with identical entries can return true when compared against this map, while this map returns false against the HashMap.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt` around lines 168 -
180, The equals implementation in CaseInsensitiveMap currently only accepts
CaseInsensitiveMap and breaks Map.equals symmetry; update
CaseInsensitiveMap.equals to accept any Map<*,*>: if other is this return true,
if other !is Map<*,*> return false, then if sizes differ return false, normalize
keys for comparison (use the same case-insensitive normalization this map uses)
and compare values for each key; reference keyStorage, valueStorage and _size to
iterate this map’s entries and compare against a normalized view of other (e.g.,
build a temporary map of other’s keys lowered/normalized when keys are String)
so lookups honor case-insensitivity and preserve Map.equals contract.
🧹 Nitpick comments (2)
ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt (1)

413-419: caseInsensitiveHashCode is duplicated verbatim in StringValues.kt (lines 327–332).

Both companion objects contain an identical private implementation. Extracting it to a shared internal top-level function (e.g., in a new CaseInsensitiveUtils.kt in the same package) would eliminate the duplication and ensure any future fix (e.g., handling of Unicode case folding) applies consistently.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt` around lines 413 -
419, The private function caseInsensitiveHashCode duplicated in
CaseInsensitiveMap.kt and StringValues.kt should be extracted to a single
internal top-level helper (e.g., create CaseInsensitiveUtils.kt in the same
package with an internal fun caseInsensitiveHashCode(s: String): Int) and both
companion objects should call that shared function; remove the duplicate private
implementations in CaseInsensitiveMap.Companion and StringValues.Companion so
the hash logic is centralized and future Unicode/case-folding fixes apply
consistently.
ktor-utils/common/src/io/ktor/util/StringValues.kt (1)

215-216: Unchecked casts on lines 215–216 are missing @Suppress("UNCHECKED_CAST").

arrayOfNulls<String>(entryCount) as Array<String> and arrayOfNulls<List<String>>(entryCount) as Array<List<String>> produce compiler warnings. Every similar cast in CaseInsensitiveMap.kt is annotated consistently; these two should be as well to keep linting clean.

🧹 Suggested fix
+            `@Suppress`("UNCHECKED_CAST")
             keyStorage = arrayOfNulls<String>(entryCount) as Array<String>
+            `@Suppress`("UNCHECKED_CAST")
             valueStorage = arrayOfNulls<List<String>>(entryCount) as Array<List<String>>
🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt` around lines 215 - 216,
Add the missing suppression for the unchecked casts used to initialize
keyStorage and valueStorage: annotate the cast expressions (or the containing
property) with `@Suppress`("UNCHECKED_CAST") so the lines using
arrayOfNulls<String>(entryCount) as Array<String> and
arrayOfNulls<List<String>>(entryCount) as Array<List<String>> no longer emit
warnings, matching the pattern used in CaseInsensitiveMap.kt; ensure the
suppression targets the same scope (the keyStorage/valueStorage initializations)
and leaves the cast logic unchanged.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 51-52: The put(key: String, value: Value) method currently calls
ensureCapacity() unconditionally which causes a full resize and rehash on pure
updates at the load-factor boundary; change it to first check whether the key
already exists (using the map's lookup helper such as indexOfKey / findSlot /
lookupKey) and if found simply replace the value and return the old one without
calling ensureCapacity(), and only call ensureCapacity() when the key is not
present and an insertion will increase _size; ensure you update the existing
entry in-place and return the previous Value when replacing.

---

Duplicate comments:
In `@gradlew.bat`:
- Around line 72-74: Remove the three consecutive blank lines left between the
two `@rem` markers by collapsing the whitespace so there is at most one blank line
(or none) between "@rem Setup the command line" and "@rem Execute Gradle"; edit
the gradlew.bat section containing those `@rem` comments to delete the extra empty
lines so the file has no leftover blank-line gap.

In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 289-290: Replace bare exception constructors with descriptive
messages: in the iterator remove() implementations for KeySet, ValueCollection,
and EntrySet (the methods named remove() that throw IllegalStateException()),
include a clear message that identifies the failed operation and the problematic
key/value (use lastKey/lastValue or equivalent local variable in the message).
Similarly, update the add() override methods that throw
UnsupportedOperationException() to provide a message stating the collection is
immutable/unsupported and include the attempted element (e.g., the parameter
element) for context; keep using the same exception types but pass a descriptive
string to the constructor.
- Around line 168-180: The equals implementation in CaseInsensitiveMap currently
only accepts CaseInsensitiveMap and breaks Map.equals symmetry; update
CaseInsensitiveMap.equals to accept any Map<*,*>: if other is this return true,
if other !is Map<*,*> return false, then if sizes differ return false, normalize
keys for comparison (use the same case-insensitive normalization this map uses)
and compare values for each key; reference keyStorage, valueStorage and _size to
iterate this map’s entries and compare against a normalized view of other (e.g.,
build a temporary map of other’s keys lowered/normalized when keys are String)
so lookups honor case-insensitivity and preserve Map.equals contract.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt`:
- Around line 183-205: The values getter currently reconstructs a case-sensitive
LinkedHashMap regardless of caseInsensitiveName; update the getter in
StringValues (the protected val values) to preserve case-insensitive semantics
by normalizing keys or using a case-insensitive Map when caseInsensitiveName is
true (e.g., insert keys.lowercase() or use a map implementation that compares
keys ignoring case) so subclasses that depend on case-insensitive lookups keep
the same behavior; ensure you still preserve insertion order (LinkedHashMap
semantics) and return emptyMap() when entryCount == 0.

---

Nitpick comments:
In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 413-419: The private function caseInsensitiveHashCode duplicated
in CaseInsensitiveMap.kt and StringValues.kt should be extracted to a single
internal top-level helper (e.g., create CaseInsensitiveUtils.kt in the same
package with an internal fun caseInsensitiveHashCode(s: String): Int) and both
companion objects should call that shared function; remove the duplicate private
implementations in CaseInsensitiveMap.Companion and StringValues.Companion so
the hash logic is centralized and future Unicode/case-folding fixes apply
consistently.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt`:
- Around line 215-216: Add the missing suppression for the unchecked casts used
to initialize keyStorage and valueStorage: annotate the cast expressions (or the
containing property) with `@Suppress`("UNCHECKED_CAST") so the lines using
arrayOfNulls<String>(entryCount) as Array<String> and
arrayOfNulls<List<String>>(entryCount) as Array<List<String>> no longer emit
warnings, matching the pattern used in CaseInsensitiveMap.kt; ensure the
suppression targets the same scope (the keyStorage/valueStorage initializations)
and leaves the cast logic unchanged.

ℹ️ Review info

Configuration used: Organization UI

Review profile: CHILL

Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between 539ff09 and 322cdfc.

📒 Files selected for processing (4)
  • gradlew.bat
  • ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
  • ktor-utils/common/src/io/ktor/util/StringValues.kt
  • ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt
🚧 Files skipped from review as they are similar to previous changes (1)
  • ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt

Comment thread ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt Outdated
Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai Bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 3

🧹 Nitpick comments (3)
ktor-utils/common/src/io/ktor/util/StringValues.kt (3)

227-227: Use value.toList() instead of List(value.size) { value[it] } for idiomatic defensive copy.

Both produce the same result (an independent ArrayList), but value.toList() is the idiomatic Kotlin idiom and avoids indexed access on a List<String> interface (which is O(n) for some implementations).

♻️ Proposed change
-                valueStorage[i] = List(value.size) { value[it] }
+                valueStorage[i] = value.toList()
🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt` at line 227, Replace the
defensive copy creation in StringValues.kt that currently uses List(value.size)
{ value[it] } with the idiomatic value.toList() to avoid O(n) indexed access on
generic List implementations; locate the assignment to valueStorage[i] in the
StringValues logic and change the copy expression so it calls value.toList()
(preserving the independent list semantics).

180-181: Constructor parameter values silently shadows the protected val values property in init.

Both values: Map<String, List<String>> (constructor parameter) and protected val values (computed property) share the same unqualified name. In Kotlin, primary-constructor parameters are in scope throughout init blocks and, as the more-local binding, shadow the class property — so values.size on line 209 resolves to the constructor parameter, not the getter. The code is correct, but the shadowing is a readability trap: a future reader or maintainer may mistake values inside init for a this.values call (which would invoke the getter with entryCount still at its default 0, silently constructing an always-empty instance).

Consider renaming the constructor parameter to initialValues to make the scoping unambiguous.

♻️ Proposed rename
 public open class StringValuesImpl(
     final override val caseInsensitiveName: Boolean = false,
-    values: Map<String, List<String>> = emptyMap()
+    initialValues: Map<String, List<String>> = emptyMap()
 ) : StringValues {
     ...
     init {
-        entryCount = values.size
+        entryCount = initialValues.size
         if (entryCount == 0) {
             ...
         } else {
             ...
-            for ((key, value) in values) {
+            for ((key, value) in initialValues) {

Also applies to: 208-209

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt` around lines 180 - 181,
The constructor parameter named values shadows the protected val values property
inside the init block (so expressions like values.size refer to the parameter,
not the property); rename the constructor parameter (e.g., to initialValues) and
update all usages inside the init and constructor signature to use that new
name, leaving the protected val values getter untouched (also update any
references to entryCount initialization that rely on the property) so there is
no ambiguity between the parameter and the computed property.

328-334: caseInsensitiveHashCode is duplicated verbatim from CaseInsensitiveMap.kt.

The same function body (identical algorithm, identical variable names) exists in the private companion object of CaseInsensitiveMap.kt (lines 426–432 per the relevant snippet). Extracting it to a shared internal utility avoids the two implementations diverging silently.

♻️ Suggested extraction

Create an internal top-level function (e.g., in ktor-utils/common/src/io/ktor/util/Strings.kt or a new CaseInsensitiveHashing.kt):

internal fun caseInsensitiveHashCode(s: String): Int {
    var h = 0
    for (i in 0 until s.length) {
        h = 31 * h + s[i].lowercaseChar().code
    }
    return h
}

Then remove the private copies from both StringValues.kt and CaseInsensitiveMap.kt companion objects and call the shared function directly.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt` around lines 328 - 334,
Duplicate private function caseInsensitiveHashCode exists in StringValues.kt and
the companion object of CaseInsensitiveMap; extract it into a single internal
top-level function (e.g., internal fun caseInsensitiveHashCode(s: String): Int)
placed in a new utility source file, then remove the private copies from both
StringValues's companion and CaseInsensitiveMap's companion and update their
callers to call the shared caseInsensitiveHashCode function; keep the
implementation identical to preserve behavior and mark the new function internal
so it’s usable across the module.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 7-12: Add a KDoc entry for the type parameter Value on the
CaseInsensitiveMap class: update the KDoc above the CaseInsensitiveMap
declaration to include a `@param` or `@tparam` description for Value (e.g., "Value —
the type of values stored in the map") so the public API documents the map's
value type; reference the CaseInsensitiveMap<Value> type parameter when adding
this brief description.
- Around line 263-395: Replace the manual null-checks that throw
IllegalStateException in the iterator remove() implementations with Kotlin's
idiomatic checkNotNull: in KeySet.remove(), ValueCollection.remove(), and
EntrySet.remove() use checkNotNull(lastKey) to validate that next() was called
before proceeding and capture the non-null key (then call
this@CaseInsensitiveMap.remove(key) and set lastKey = null); reference the
iterator classes KeySet, ValueCollection, EntrySet and their private var lastKey
fields when making this change.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt`:
- Around line 247-254: names() currently builds a LinkedHashSet<String> directly
which ignores the case-insensitive semantics; change names() to follow the
values getter pattern (around line 201) by constructing a LinkedHashMap (or
whichever map is used there) conditionally with case-insensitive key handling
when caseInsensitiveName is true, populate it with keyStorage[0..entryCount-1]
-> dummy values, and then return that map.keys so the resulting Set<String> has
case-insensitive contains() behavior while preserving insertion order.

---

Nitpick comments:
In `@ktor-utils/common/src/io/ktor/util/StringValues.kt`:
- Line 227: Replace the defensive copy creation in StringValues.kt that
currently uses List(value.size) { value[it] } with the idiomatic value.toList()
to avoid O(n) indexed access on generic List implementations; locate the
assignment to valueStorage[i] in the StringValues logic and change the copy
expression so it calls value.toList() (preserving the independent list
semantics).
- Around line 180-181: The constructor parameter named values shadows the
protected val values property inside the init block (so expressions like
values.size refer to the parameter, not the property); rename the constructor
parameter (e.g., to initialValues) and update all usages inside the init and
constructor signature to use that new name, leaving the protected val values
getter untouched (also update any references to entryCount initialization that
rely on the property) so there is no ambiguity between the parameter and the
computed property.
- Around line 328-334: Duplicate private function caseInsensitiveHashCode exists
in StringValues.kt and the companion object of CaseInsensitiveMap; extract it
into a single internal top-level function (e.g., internal fun
caseInsensitiveHashCode(s: String): Int) placed in a new utility source file,
then remove the private copies from both StringValues's companion and
CaseInsensitiveMap's companion and update their callers to call the shared
caseInsensitiveHashCode function; keep the implementation identical to preserve
behavior and mark the new function internal so it’s usable across the module.

ℹ️ Review info

Configuration used: Organization UI

Review profile: CHILL

Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between 322cdfc and 60345b2.

📒 Files selected for processing (3)
  • ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
  • ktor-utils/common/src/io/ktor/util/StringValues.kt
  • ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt
🚧 Files skipped from review as they are similar to previous changes (1)
  • ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt

Comment thread ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
Comment thread ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
Comment thread ktor-utils/common/src/io/ktor/util/StringValues.kt
@e5l e5l requested a review from osipxd February 26, 2026 12:06
@osipxd osipxd changed the title CaseInsensitiveMap and StringValuesImpl: zero-allocation header storage KTOR-9383 CaseInsensitiveMap and StringValuesImpl: zero-allocation header storage Mar 2, 2026
Copy link
Copy Markdown
Member

@osipxd osipxd left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Two blocking issues with concrete repros are noted inline.

if (other == null || other !is CaseInsensitiveMap<*>) return false
return other.delegate == delegate
if (other === this) return true
if (other !is Map<*, *>) return false
Copy link
Copy Markdown
Member

@osipxd osipxd Mar 5, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

equals now accepts any Map<*, *> and compares keys case-insensitively, but hashCode stays case-insensitive-only. This breaks the equals/hashCode contract against regular maps: equal objects must have equal hash codes.

Repro:

import io.ktor.util.CaseInsensitiveMap;
import java.util.HashMap;

var m = new CaseInsensitiveMap<String>();
m.put("Foo", "1");

var r = new HashMap<String, String>();
r.put("Foo", "1");

System.out.println("m.equals(r)=" + m.equals(r));
System.out.println("r.equals(m)=" + r.equals(m));
System.out.println("m.hashCode=" + m.hashCode());
System.out.println("r.hashCode=" + r.hashCode());

Observed:

  • m.equals(r)=true
  • r.equals(m)=true
  • m.hashCode=101623
  • r.hashCode=70807

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The current implementation restricts equals() to only accept CaseInsensitiveMap instances. This avoids the hashCode mismatch you reported, but it means CaseInsensitiveMap won't compare equal to a regular HashMap with identical entries.

The fundamental tension: if we accept any Map in equals(), then hashCode() must produce the same value for equal maps. But a standard HashMap uses key.hashCode() while we use case-insensitive hashing. Two options:

(A) Keep equals restricted to CaseInsensitiveMap only (current) — consistent hashCode, but breaks Map.equals contract with other Map implementations
(B) Accept any Map in equals, switch hashCode to use standard key.hashCode() — this means CaseInsensitiveMap("Foo"->1).equals(HashMap("Foo"->1)) works, but CaseInsensitiveMap("Foo"->1) and CaseInsensitiveMap("foo"->1) would have different hashCodes despite being logically equal

Which approach do you prefer?

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Going with option (A): equals() is restricted to CaseInsensitiveMap instances only (already implemented). This keeps hashCode() consistent (case-insensitive hashing) and avoids the contract violation. The trade-off is that CaseInsensitiveMap won't compare equal to a regular HashMap with identical entries, which is acceptable for our use case.

hashNext = IntArray(entryCount) { -1 }

var i = 0
for ((key, value) in values) {
Copy link
Copy Markdown
Member

@osipxd osipxd Mar 5, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For caseInsensitiveName = true, constructor input is no longer canonicalized through caseInsensitiveMap(). Case variants like "A" and "a" are both retained in names()/entries(), while lookup returns only one chain winner. That regresses previous behavior and makes observable state inconsistent for case-insensitive values.

Repro:

import io.ktor.util.StringValuesImpl;
import java.util.Map;
import java.util.List;

var sv = new StringValuesImpl(true, Map.of("A", List.of("1"), "a", List.of("2")));

System.out.println("names=" + sv.names());
System.out.println("entries=" + sv.entries());
System.out.println("getAll(a)=" + sv.getAll("a"));

Observed on this PR:

  • names=[A, a]
  • entries=[A=[1], a=[2]]
  • getAll(a)=[2]

Baseline (ktor-utils-jvm-3.4.1-SNAPSHOT) for same snippet:

  • names=[A]
  • entries=[A=[2]]
  • getAll(a)=[2]

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could you also add a test for this case?

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done. Added test case-insensitive constructor deduplicates keys that differ by case in StringValuesTest.

override val size: Int get() = _size

override fun add(element: Value): Boolean =
throw UnsupportedOperationException("CaseInsensitiveMap.values is read-only")
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This error states that the map is read-only, but we have remove() implementation

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed. Changed error messages from "is read-only" to "does not support add" for KeySet.add() and EntrySet.add().

Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai Bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 1

♻️ Duplicate comments (1)
ktor-utils/common/src/io/ktor/util/StringValues.kt (1)

280-287: ⚠️ Potential issue | 🟠 Major

names() still returns a case-sensitive set, breaking case-insensitive lookup semantics.

The current implementation uses linkedSetOf<String>() regardless of caseInsensitiveName. This causes names().contains("content-type") to return false when the stored key is "Content-Type", even though the instance is case-insensitive.

This is inconsistent with the values getter (line 200-201), which correctly uses caseInsensitiveMap() conditionally.

Proposed fix to match the values getter pattern
 override fun names(): Set<String> {
     if (entryCount == 0) return emptySet()
-    val result = linkedSetOf<String>()
+    val result: MutableMap<String, Unit> =
+        if (caseInsensitiveName) caseInsensitiveMap() else LinkedHashMap(entryCount)
     for (i in 0 until entryCount) {
-        result.add(keyStorage[i])
+        result[keyStorage[i]] = Unit
     }
-    return result
+    return result.keys
 }
🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/StringValues.kt` around lines 280 - 287,
The names() implementation returns a case-sensitive linkedSet regardless of
caseInsensitiveName, breaking case-insensitive semantics; update names() (which
reads entryCount and keyStorage) to create the result set using the same
conditional used by the values getter—i.e., when caseInsensitiveName is true,
construct a case-insensitive set (using the project's case-insensitive
collection factory used elsewhere, e.g., caseInsensitiveMap()/set variant) and
otherwise use linkedSetOf<String>(), then add keyStorage[i] into that set and
return it.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 258-260: Update the exception messages in KeySet.add and
EntrySet.add to match the updated wording used in ValueCollection.add: replace
"is read-only" with "does not support add". Locate the methods
KeySet.add(element: String): Boolean and EntrySet.add(element: Map.Entry<String,
Any?>): Boolean and change the UnsupportedOperationException message to "does
not support add" so the behavior and wording are consistent across the
collection views.

---

Duplicate comments:
In `@ktor-utils/common/src/io/ktor/util/StringValues.kt`:
- Around line 280-287: The names() implementation returns a case-sensitive
linkedSet regardless of caseInsensitiveName, breaking case-insensitive
semantics; update names() (which reads entryCount and keyStorage) to create the
result set using the same conditional used by the values getter—i.e., when
caseInsensitiveName is true, construct a case-insensitive set (using the
project's case-insensitive collection factory used elsewhere, e.g.,
caseInsensitiveMap()/set variant) and otherwise use linkedSetOf<String>(), then
add keyStorage[i] into that set and return it.
🪄 Autofix (Beta)

Fix all unresolved CodeRabbit comments on this PR:

  • Push a commit to this branch (recommended)
  • Create a new PR with the fixes

ℹ️ Review info
⚙️ Run configuration

Configuration used: Path: .coderabbit.yaml

Review profile: CHILL

Plan: Pro

Run ID: e6fd56b8-0a6d-4da6-868f-1e5051732046

📥 Commits

Reviewing files that changed from the base of the PR and between 60345b2 and 2c2e653.

📒 Files selected for processing (3)
  • ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
  • ktor-utils/common/src/io/ktor/util/StringValues.kt
  • ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt

Comment thread ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
@bjhham
Copy link
Copy Markdown
Contributor

bjhham commented Mar 17, 2026

It seems this increases allocations in the client:

Request consumes 35.01 KB, expected 30.61 KB.
  Difference: 4504 > 3762 (allowed)
  Consumed 35.01 KB on request
  Expected 30.61 KB on request
  Extra    4504 bytes on request
(See stdout + build/allocations/* files for details)
Increased locations:
  CaseInsensitiveMap.kt                         2168    (3720         -->         5888)
  StringValues.kt                               1208    (784          -->         1992)
  DateJvm.kt                                     960    (112          -->         1072)
  URLBuilder.kt                                  840    (3704         -->         4544)
  HttpPlainText.kt                               312    (96           -->          408)
  Collections.kt                                 256    (384          -->          640)
  JavaHttpRequest.kt                             152    (744          -->          896)
  Utils.kt                                       136    (232          -->          368)
  JavaHttpResponse.kt                             97    (2804         -->         2901)
  URLUtils.kt                                     80    (488          -->          568)
  Headers.kt                                      64    (96           -->          160)
  HttpClientEngine.kt                             32    (1592         -->         1624)
  Parameters.kt                                   32    (336          -->          368)
  JavaHttpResponseBodyHandler.kt                  16    (1728         -->         1744)

@e5l e5l enabled auto-merge (squash) March 18, 2026 08:59
Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai Bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 1

♻️ Duplicate comments (1)
ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt (1)

174-186: ⚠️ Potential issue | 🟠 Major

equals is constrained to CaseInsensitiveMap only, which is surprising for a MutableMap implementation.

This blocks normal cross-Map equality expectations and should either be aligned with Map<*, *> comparison semantics or explicitly documented as an intentional divergence in public KDoc.

Kotlin Map.equals contract for custom MutableMap implementations: should equality be based on mapping equivalence across different Map implementations?

Based on learnings: Applies to **/*.kt : All public/protected API changes must be intentional and well-documented.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt` around lines 174 -
186, The equals implementation in CaseInsensitiveMap is incorrectly constrained
to CaseInsensitiveMap and should follow Map<*,*> semantics: change equals(other:
Any?) in class CaseInsensitiveMap to accept any Map implementation, return true
when mappings are equivalent regardless of concrete type, and preserve
referential equality and size checks; specifically, if other is a Map<*,*> check
size == _size and then for each non-null key in keyStorage compare
valueStorage[i] to other[normalizedKey] (handling nulls correctly) or
alternately iterate other.entries and ensure this[key] == entry.value for all
entries; update logic to handle keys absent vs present-with-null values and keep
early-return for inequality. Reference: equals, CaseInsensitiveMap, keyStorage,
valueStorage, _size.
🧹 Nitpick comments (1)
ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt (1)

419-424: Consider extracting the case-insensitive hash function to a shared internal utility.

CaseInsensitiveMap.kt and StringValues.kt currently carry identical logic; centralizing avoids drift between two hash-based data structures that are meant to stay compatible.

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt` around lines 419 -
424, Extract the duplicate case-insensitive hashing logic into a single internal
utility function (e.g., internal fun caseInsensitiveHashCode(s: String): Int)
and remove the copies from CaseInsensitiveMap.kt and StringValues.kt; update
both CaseInsensitiveMap (where caseInsensitiveHashCode was used) and the
StringValues implementation to call the new shared utility so both data
structures remain bit‑for‑bit compatible, keep the function internal/visible to
the module, preserve the current algorithm (lowercaseChar()/code and 31
multiplier) and run/update any relevant tests that depend on hashing behavior.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 165-172: The getters for keys, entries, and values in
CaseInsensitiveMap currently allocate a new KeySet/EntrySet/ValueCollection on
every access; modify the CaseInsensitiveMap class to create and cache single
instances (e.g., private val cachedKeySet, cachedEntrySet, cachedValueCollection
initialized lazily or at construction) and have the overrides of keys, entries,
and values return those cached objects instead of new
KeySet()/EntrySet()/ValueCollection() each call; ensure the cached views reflect
mutations of the underlying map (reuse existing inner classes KeySet, EntrySet,
ValueCollection) and update any visibility/initialization accordingly.

---

Duplicate comments:
In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 174-186: The equals implementation in CaseInsensitiveMap is
incorrectly constrained to CaseInsensitiveMap and should follow Map<*,*>
semantics: change equals(other: Any?) in class CaseInsensitiveMap to accept any
Map implementation, return true when mappings are equivalent regardless of
concrete type, and preserve referential equality and size checks; specifically,
if other is a Map<*,*> check size == _size and then for each non-null key in
keyStorage compare valueStorage[i] to other[normalizedKey] (handling nulls
correctly) or alternately iterate other.entries and ensure this[key] ==
entry.value for all entries; update logic to handle keys absent vs
present-with-null values and keep early-return for inequality. Reference:
equals, CaseInsensitiveMap, keyStorage, valueStorage, _size.

---

Nitpick comments:
In `@ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt`:
- Around line 419-424: Extract the duplicate case-insensitive hashing logic into
a single internal utility function (e.g., internal fun
caseInsensitiveHashCode(s: String): Int) and remove the copies from
CaseInsensitiveMap.kt and StringValues.kt; update both CaseInsensitiveMap (where
caseInsensitiveHashCode was used) and the StringValues implementation to call
the new shared utility so both data structures remain bit‑for‑bit compatible,
keep the function internal/visible to the module, preserve the current algorithm
(lowercaseChar()/code and 31 multiplier) and run/update any relevant tests that
depend on hashing behavior.
🪄 Autofix (Beta)

Fix all unresolved CodeRabbit comments on this PR:

  • Push a commit to this branch (recommended)
  • Create a new PR with the fixes

ℹ️ Review info
⚙️ Run configuration

Configuration used: Path: .coderabbit.yaml

Review profile: CHILL

Plan: Pro

Run ID: 6c418df4-173b-48e0-880f-e4f3298b6aba

📥 Commits

Reviewing files that changed from the base of the PR and between 2c2e653 and a566ac1.

📒 Files selected for processing (3)
  • ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt
  • ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt
  • ktor-utils/common/test/io/ktor/util/StringValuesTest.kt
🚧 Files skipped from review as they are similar to previous changes (1)
  • ktor-utils/common/test/io/ktor/util/CaseInsensitiveMapTest.kt

Comment thread ktor-utils/common/src/io/ktor/util/CaseInsensitiveMap.kt Outdated
@e5l
Copy link
Copy Markdown
Member Author

e5l commented Mar 18, 2026

Addressed review feedback:

  • Fixed CaseInsensitiveMapTest that was failing on native/JS/Wasm: assertNotEquals(map, regular) was testing regular.equals(map) (HashMap direction) which returns true. Changed to assertFalse(map.equals(regular)) to test only the direction we control.
  • Fixed error messages in KeySet.add() and EntrySet.add() — changed from "is read-only" to "does not support add" since remove() is supported (as requested by @osipxd in comment)
  • Added test for StringValuesImpl case-insensitive constructor key deduplication (as requested by @osipxd in comment)

CI results after fix:

  • ✅ JavaScript on Chrome/Node.js — now passes (was failing)
  • ✅ WasmJS on Chrome/Node.js — now passes (was failing)
  • ✅ Native Linux X64 — now passes (was failing)
  • ✅ Java 11 on Linux — passes
  • ✅ Check ABI, Check JPMS, CodeStyle — pass
  • ❌ Allocation tests — still failing (known issue, tracked in @bjhham's comment)
  • ❌ Java 8/17/21, Native macOS/Windows — failures are unrelated flaky tests (Jetty HTTP/2, ClientCert, HttpTimeout, Curl)

Remaining open item: the allocation test regressions reported by @bjhham need to be addressed separately.

@e5l
Copy link
Copy Markdown
Member Author

e5l commented Mar 18, 2026

Addressed review feedback (iteration 2):

Fixed:

  • Allocation regression (reported by @bjhham): Reduced CaseInsensitiveMap allocations by lazy-initializing backing arrays on first put() (empty maps now allocate zero arrays), caching KeySet/EntrySet/ValueCollection instances to avoid per-access allocation, and reducing INITIAL_CAPACITY from 16 to 8. Allocation tests now pass.

Previously fixed (iteration 1):

  • Fixed CaseInsensitiveMapTest for native/JS/Wasm platforms
  • Fixed error messages in KeySet.add() and EntrySet.add() (as requested by @osipxd)
  • Added test for StringValuesImpl case-insensitive constructor key deduplication (as requested by @osipxd)

Asked clarifying question:

  • equals/hashCode contract (comment thread with @osipxd): Posted question with two concrete options (A) restrict equals to CaseInsensitiveMap only, or (B) accept any Map with standard hashCode

CI status after this push:

  • ✅ Allocation tests — now passing
  • ✅ Java 8, 11 — pass
  • ✅ JavaScript, WasmJS, Native Linux X64, Native macOS X64 — pass
  • ✅ Check ABI, Check JPMS, CodeStyle — pass
  • ❌ Java 17, 21 — ClientCert tests (failing since #7152, pre-existing) + flaky server tests
  • ❌ Native Windows X64, macOS Arm64 — flaky Curl/Darwin tests (pre-existing)

Copy link
Copy Markdown
Member

@osipxd osipxd left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please rebase onto the latest main or release/3.x. Currently this branch lacks improvements that have been merged into release and main branches. So benchmark results doesn't reflect the real situation.

Request consumes 18.67 KB, expected 18.26 KB.
  Difference: 418 < 2244 (allowed)
  Consumed 18.67 KB on request
  Expected 18.26 KB on request
  Extra    418 bytes on request
(See stdout + build/allocations/* files for details)
Increased locations:
  HttpProtocolVersion.kt                        1632    (0            -->         1632)
  StringValues.kt                                192    (160          -->          352)
  Collections.kt                                 112    (128          -->          240)
  Parameters.kt                                   48    (168          -->          216)
Decreased locations:
  CaseInsensitiveMap.kt                         -904    (1088         -->          184)
  DelegatingMutableSet.kt                       -336    (336          -->            0)
  Text.kt                                       -240    (240          -->            0)
  Pipeline.kt                                    -68    (562          -->          494)
  CollectionsJvm.kt                              -16    (16           -->            0)
  ByteChannel.kt                                  -1    (1561         -->         1560)
  ActorSelectorManager.kt                         -1    (640          -->          639)

e5l and others added 5 commits March 19, 2026 11:15
Replace CaseInsensitiveString wrapper-based map with open-addressing hash
table using linear probing. Replace List-based StringValuesImpl with
parallel arrays and hash table for O(1) lookup and zero-allocation forEach.

Eliminates ~2,474 allocation samples per profiling run.

Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
… values accessor, add exception messages, rename tests

Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
- CaseInsensitiveMap.equals() now only accepts CaseInsensitiveMap to
  preserve the equals/hashCode contract (case-insensitive hashing is
  inconsistent with regular Map hashing)
- StringValuesImpl init block deduplicates keys case-insensitively
  when caseInsensitiveName=true, merging values for duplicate keys
- ValueCollection.add() error message changed from "is read-only"
  to "does not support add" since remove() is supported

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>
- Fix equals test to use assertFalse(map.equals(regular)) instead of
  assertNotEquals which tests the reverse direction and fails on
  native/JS where HashMap.equals(CaseInsensitiveMap) returns true
- Fix error messages in KeySet.add() and EntrySet.add() to say
  "does not support add" instead of "is read-only" since remove() is supported
- Add test for StringValuesImpl case-insensitive constructor key deduplication

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>
- Reduce CaseInsensitiveMap allocations: lazy-initialize backing arrays on
  first put() instead of at construction time (empty maps allocate nothing)
- Cache KeySet/EntrySet/ValueCollection instances to avoid per-access allocation
- Reduce INITIAL_CAPACITY from 16 to 8 to better match typical header counts

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>
@e5l
Copy link
Copy Markdown
Member Author

e5l commented Mar 19, 2026

Iteration 3 — CI investigation (no code changes needed)

All review feedback from previous iterations remains addressed. No new reviewer comments.

CI failures investigated — all are flaky tests unrelated to this PR:

All failing tests pass locally. The failures are in modules not touched by this PR (ktor-client-cio, ktor-server-netty, ktor-server-cio, ktor-client-okhttp, ktor-client-curl) and are caused by timing/network/concurrency issues:

Test Platform Root cause
ContentTest.testEmptyContent macOS/Windows/macOSx64 ConcurrentModificationException in ConcurrentMapNative.entries — raw delegate view mutated during iteration in CIOEngine.close()
DarwinLegacyEngineTest.testRequestInRunBlocking macOS Arm64 Coroutine timeout (1s)
DarwinLegacyEngineTest.testQueryWithCyrillic macOS Arm64 Uncompleted coroutines timeout
CurlHttp2Test.test protocol version is HTTP 2 Windows Failing since build #3886 — unrelated to this PR
Various Netty/CIO/OkHttp tests JVM Network timeouts, socket closes, H2 inactivity timeouts

Action taken:

Copy link
Copy Markdown
Member

@osipxd osipxd left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice!

Request consumes 43.86 KB, expected 46.22 KB.
  Difference: -2414 < 5679 (allowed)
  Consumed 43.86 KB on request
  Expected 46.22 KB on request
  Saved    2414 bytes on request

Increased locations:
  StringValues.kt                                768    (720          -->         1488)
  Collections.kt                                 576    (384          -->          960)
  Headers.kt                                      64    (96           -->          160)
  ByteChannel.kt                                  40    (2755         -->         2795)
  HttpClientEngine.kt                             32    (1568         -->         1600)
  Parameters.kt                                   32    (336          -->          368)
  SocketBase.kt                                   22    (475          -->          497)
  utils.kt                                         9    (2562         -->         2571)
  ByteWriteChannelOperations.kt                    4    (2136         -->         2140)
  ByteChannelUtils.kt                              2    (109          -->          111)
  ActorSelectorManager.kt                          1    (1410         -->         1411)
Decreased locations:
  CaseInsensitiveMap.kt                        -1976    (3720         -->         1744)
  DelegatingMutableSet.kt                      -1400    (1400         -->            0)
  Text.kt                                       -528    (528          -->            0)
  CollectionsJvm.kt                              -32    (224          -->          192)
  DefaultRequest.kt                              -24    (696          -->          672)
  ByteReadChannelOperations.kt                    -4    (3169         -->         3165)

@e5l e5l merged commit c91aa74 into main Mar 19, 2026
16 of 19 checks passed
@e5l e5l deleted the e5l/opt-1-case-insensitive-map branch March 19, 2026 16:18
osipxd pushed a commit that referenced this pull request Mar 19, 2026
…ader storage (#5379)

* CaseInsensitiveMap and StringValuesImpl: zero-allocation header storage

Replace CaseInsensitiveString wrapper-based map with open-addressing hash
table using linear probing. Replace List-based StringValuesImpl with
parallel arrays and hash table for O(1) lookup and zero-allocation forEach.

Eliminates ~2,474 allocation samples per profiling run.

Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>

* Address review comments: fix Map.equals contract, optimize put(), fix values accessor, add exception messages, rename tests

Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>

* Fix equals/hashCode contract, key deduplication, and error message

- CaseInsensitiveMap.equals() now only accepts CaseInsensitiveMap to
  preserve the equals/hashCode contract (case-insensitive hashing is
  inconsistent with regular Map hashing)
- StringValuesImpl init block deduplicates keys case-insensitively
  when caseInsensitiveName=true, merging values for duplicate keys
- ValueCollection.add() error message changed from "is read-only"
  to "does not support add" since remove() is supported

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>

* Address review feedback (iteration 1)

- Fix equals test to use assertFalse(map.equals(regular)) instead of
  assertNotEquals which tests the reverse direction and fails on
  native/JS where HashMap.equals(CaseInsensitiveMap) returns true
- Fix error messages in KeySet.add() and EntrySet.add() to say
  "does not support add" instead of "is read-only" since remove() is supported
- Add test for StringValuesImpl case-insensitive constructor key deduplication

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>

* Address review feedback (iteration 2)

- Reduce CaseInsensitiveMap allocations: lazy-initialize backing arrays on
  first put() instead of at construction time (empty maps allocate nothing)
- Cache KeySet/EntrySet/ValueCollection instances to avoid per-access allocation
- Reduce INITIAL_CAPACITY from 16 to 8 to better match typical header counts

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>

---------

Co-authored-by: Claude Opus 4.6 <noreply@anthropic.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants