DEV Community: Dash One

Introducing SafeSql - Enforced Injection Safety

Dash One — Thu, 17 Jul 2025 01:33:07 +0000

SQL Injection

In Java, JDBC PreparedStatement is the vital defense against SQL Injection (SQLi).

However when developers need to build dynamic SQL (imagine if you need to parameterize by table name, column names, or have complex subqueries to reuse), PreparedStatement's parameterization support becomes insufficient and they usually have to fall back to raw string concatenation, opening the door to injection risks.

NotPetya (2017) – Up to $10 Billion: This ransomware attack, which exploited initial vulnerabilities that could include web application flaws, caused unprecedented global disruption and staggering financial losses for giants like Maersk and FedEx.
Equifax (2017) – Over $1.4 Billion: A failure to patch a known web application vulnerability exposed sensitive data for 147 million people, leading to massive settlements, fines, and enduring reputational damage.

When large, complex systems rely on programmer caution and code reviews for dynamic SQL string concatenation, the risk is a timed bomb. Human errors, vast codebase, developer turnover, and rushed reviews make it impossible to manually prevent every subtle SQLi vulnerability.

Humans make mistake, they always do.

Existing Mitigations

Hardening the SQL String

Google internally uses the TrustedSqlString class. By taking advantage of ErrorProne's compile-time check, it ensures that only trusted sql snippets (compile-time string constants, flag values etc.) are allowed to be concatenated.

The Spanner library builds on top of TrustedSqlString, by supporting bind("id", id) calls for named parameters like @id.

It works, but when you have complex subqueries to be composed together, each with their own parameters, you'll have to manage and merge the parameters yourself, making sure the parameter names don't clash etc.

This can still result in fragmented SQL and complex parameter managing code.

SQL Template With Escape Hatch

MyBatis offers the #{} syntax for filling in template parameters and passing them as PreparedStatement parameters.

For dynamic SQL (table names etc.), the ${} syntax is used to allow developers to fill in arbitrary string, an escape hatch and a "be careful, you are on your own" warning.

The ${} escape hatch is not only a door to SQLi, it can also be confusing to developers about which is what, adding human errors to the attackers' ammunition.

Java DSL

Another mitigation is to switch to what I call "DSL-first" approach (as opposed to "SQL-first", where you write real SQL.

So instead of select id, name from users where name like '%foo%', you write:

select(ID, NAME).from(USERS).where(NAME.like("%" + name + "%"))

The upside is that the DSL won't accept arbitrary concatenated string. And because the DSL result is a Java object, you can compose them, with both the subquery SQL and its parameters.

The downsides however are also pretty glaring:

You write in Java DSL, NOT SQL. You can't easily copy and paste between your Java source code and your DB console to debug and test your SQL.
You can't easily parameterize by table name or column names, unless you make an escape hatch, which then leaves the door to injection widely open.
While IDE auto-completion feels nice for Java devs, when the SQL grows long and complex, it's more mentally taxing to have to first translate the DSL into SQL in your head before you can reason about it (it's leaky abstraction).
Quirks like operator precedence divergence (a.or(b).and(c) reads like a OR b AND c but is different) can be confusing and dangerous-they result in silent behavior bug and may cause data corruption.

`SafeSql`

Before we dive into details, here's an intuitive example:

SafeSql sql = SafeSql.of(
    "select id, name from users where name like '%{name}%'",
    name);
List<User> users = sql.query(dataSource, User.class);

How Does `SafeSql` Prevent SQLi?

SafeSql is heavily influenced by Google's TrustedSqlString technique: it uses ErrorProne to ensure only compile-time constants can be used as the SQL template.

But it takes one step further by encapsulating the parameters with the sql template as a higher-level SafeSql object that can be passed around and composed, kinda like JEP 459's SQL processor.

SafeSql then enforces that all value parameters are passed through PreparedStatement's parameterization.

The only types of parameters that are directly embedded in the SQL string are:

Another SafeSql object, which is already validated to be safe from inection.
backtick-quoted or double-quoted placeholders like "{user_table}" are validated to only include characters that can be safely used as an identifier.

There is simply no way for an unsuspecting developer to accidentally inject malicious code. If SafeSql compiles and runs, it's provably safe from SQLi.

Next let's look at a few reasl world examples

Dynamic `IN` Clauses with Collections

When using an IN clause, most frameworks require you to manually construct the right number of placeholders, which can be cumbersome and error-prone.

Example (MyBatis XML):

<!-- Using MyBatis <foreach> to handle dynamic IN lists -->
<select id="findByDepartmentIds" resultType="User">
  SELECT * FROM Sales
  WHERE department_id IN
  <foreach item="id" collection="departmentIds" open="(" separator="," close=")">
    #{id}
  </foreach>
</select>

// Called with:
sqlSession.selectList("findByDepartmentIds", Map.of("departmentIds", List.of(1, 2, 3)));

It's safe from SQL injection (if you correctly used #{}, not ${}). But it requires the special <foreach> XML syntax, which adds visual clutter and complexity compared to writing plain SQL.

With SafeSql:

List<Integer> departmentIds = List.of(1, 2, 3);
SafeSql.of(
    "SELECT * FROM Sales WHERE department_id IN ({department_ids})",
    departmentIds);

SafeSql automatically expands the list parameter {department_ids} to the correct number of placeholders and binds the values, eliminating manual string work and preventing common mistakes.

Conditional Query Fragments

Adding optional filters or groupings usually means string concatenation or awkward branching in your code.

Example (with manual concatenation):

String sql = "SELECT * FROM Sales";
if (groupByDay) {
    sql += " GROUP BY department_id, date";
} else {
    sql += " GROUP BY department_id";
}

Manually stitching together query fragments can quickly become hard to read and maintain, and makes errors or injection bugs more likely.

With SafeSql:

SafeSql.of(
    """
    SELECT department_id {group_by_day -> , date}, COUNT(*) AS cnt
    FROM Sales
    WHERE department_id IN ({department_ids})
    GROUP BY department_id {group_by_day -> , date},
    """,
    groupByDay, departmentIds, groupByDay);

The -> guard in {group_by_day -> , date} tells SafeSql to conditionally include , date wherever needed based on the value of groupByDay. This keeps dynamic queries clean and makes logic explicit at the SQL level, not hidden in string operations.

Injecting Identifiers like Column or Table Names

Most frameworks only allow safe parameterization for values, because the JDBC PreparedStatement only supports value parameterization. When it comes to parameterizing SQL identifiers, such as table names or column names, developers are forced to fall back to direct string concatenation.

Example (in MyBatis XML):

<select id="findMetrics" resultType="Map">
  SELECT department_id, date, ${metricColumns}
  FROM Sales
</select>

// When called as:
sqlSession.selectList("findMetrics", Map.of("metricColumns", "price, currency, discount"));
// Generates:
SELECT department_id, date, price, currency, discount FROM Sales

In MyBatis, #{} is for safe value parameterization—these become JDBC parameters and are properly escaped.
${} is direct string substitution—raw and unescaped.
Using ${metricColumns} means whatever string is supplied is injected as-is into the SQL.
- This creates a serious SQL injection risk if any part of the input comes from user data.
The similarity between #{} (JDBC parameterized) and ${} (please inject me!) is a frequent source of confusion and mistakes.

With SafeSql:

Simply backtick-quote (or double-quote, whichever your DB uses to quote identifiers) the placeholder and SafeSql will recognize the intention to use it as an identifier:

List<String> metricColumns = List.of("price", "currency", "discount");
SafeSql.of("SELECT department_id, date, `{metric_columns}` FROM Sales", metricColumns);

SafeSql expands {metric_columns} into a comma-separated, properly quoted, and validated list of identifiers. Unsafe or invalid names are rejected, which removes a whole class of injection risks and makes the query easy to audit.

Proper Escaping for LIKE Patterns

When user input is used in LIKE queries, forgetting to escape % or _ can cause accidental matches or security issues.

Example (with manual escaping):

String term = userInput.replace("%", "\%").replace("_", "\_");
String sql = "SELECT * FROM users WHERE name LIKE ?";
jdbcTemplate.query(sql, term);

Manual escaping is repetitive and easy to forget, leading to unpredictable results or vulnerabilities.

With SafeSql:

SafeSql.of("SELECT * FROM users WHERE name LIKE '%{name}%'", userName);

SafeSql escapes any special characters in parameters used within LIKE expressions automatically. You don’t have to think about escaping rules or risk mistakes—user input is always treated literally.

Query Composition and Parameter Isolation

Composing queries from reusable fragments often leads to parameter name clashes or incorrect bindings, especially as code grows.

With manual tracking, you have to carefully manage names and argument lists, often by inventing your own conventions, which makes code hard to read and can break during refactorings.

It’s easy to accidentally overwrite or mismatch parameters, leading to subtle bugs or unexpected results.

With SafeSql:

SafeSql computation = SafeSql.of("CASE ... END as computed, {from_time}", fromTime);
SafeSql whereClause = ...;
SafeSql.of(
    """
    SELECT department_id, {computation}
    FROM Sales
    WHERE {where_clause}
    """,
    computation, whereClause);

Each fragment’s parameters are managed in isolation by SafeSql, so you can safely compose and reuse query parts without worrying about accidental overwrites or binding mistakes. They are guaranteed to be eventually sent through PreparedStatement in the correct order.

Parameter Name and Order Checking

In traditional frameworks, parameter order or name mismatches can slip by the compiler and only fail at runtime—or worse, silently produce incorrect results.

Example (with JDBC):

String sql = "SELECT * FROM users WHERE id = ? AND name = ?";
preparedStatement.setInt(1, userName); // mistake: wrong order
preparedStatement.setString(2, userId);

Example (with Spring NamedParameterJdbcTemplate):

new NamedParameterJdbcTemplate(dataSource)
    .queryForList(
        "SELECT * FROM users WHERE id = :id AND name = :name",
        Map.of("nmae", userName, "id", userId));  // typo!

This kind of error won’t always be caught during development, and can be difficult to debug.

With SafeSql:
SafeSql integrates with ErrorProne to check at compile time that the template placeholders and the template arguments match. If you get the order or number of arguments wrong, you’ll get a clear compilation error.

For example, the following code will fail to compile because the order of the two arguments is wrong:

SafeSql.of(
    """
    select id, name, age from users
    where id = {id} OR name LIKE '%{name}%'
    """,
    userName, userId);

Such compile-time check is very useful when your SQL is large and you need to change or move a snippet around, which can cause the placeholders no longer matching the template arguments.

Sometimes you may run into a placeholder name that doesn't match the corresponding argument expression. If renaming the placeholder isn't an option, consider using an explicit comment like the following:

SafeSql.of(
    """
    select id, name, age
    from users
    where id = {user_id} OR name LIKE '%{user_name}%'
    """,
    /* user_id */ userRequest.getUuid(), userRequest.getUserName());

The explicit /* user_id */ confirms your intention to both SafeSql and to your readers that you do mean to use the uuid as the user_id.

Type Safety

SafeSql doesn't know your database schema so cannot check for column types or column name typos.

But typos and superficial type mismatch (like using int for the name column) are the easy kind of errors:

If you test your SQL (and you should), the DB will instantly catch these errors for you.
- In fact, it's best if you've copied the SQL from the DB console where the correctness is already verified.
- And you should have automated tests to ensure the SQL not only type checks, but gives you the right result.
Most db types are numbers and strings. So the type checking can only provide marginal protection anyways.
False sense of security is dangerous. If you ever wish to skip testing your SQL because it "type checks", then it's a liability.

The main safety advantages of SafeSql are in its zero-backdoor SQL injection prevention, compile-time semantic check such that you can't pass user.name() in the place of {ssn} despite both being string, as well as automatic parameter wiring, and convenient dynamic query construction—areas where mistakes are easy to make and hard to find otherwise.

Summary

In a nutshell, use SafeSql if any of the following applies to you:

You are a large enterprise. Relying on developer vigilance to avoid SQL injection isn't an option. Instead, you need systematically enforced safety.
You prefer to write actual SQL, and appreciate the ability to directly copy-paste queries between your code and the database console for easy debugging and testing.
A low learning curve and a what-you-see-is-what-you-get (WYSIWYG) approach are important to you. No Domain Specific Language (DSL) to learn.
You need to parameterize by table names, column names, all while preventing injection risks.
You have dynamic and complex subqueries to compose. And you find it error prone managing the subquery parameters manually.
You value compile-time semantic error prevention so you won't accidentally use user.name() in a place intended for {ssn}, even if both are strings.

Designing a Better String Utility - Part 2

Dash One — Thu, 19 Jun 2025 16:44:20 +0000

Part 2: Designing a Better String Utility

In Part 1, we saw that everyday string manipulation is surprisingly brittle. So let’s try designing something better—from scratch.

🔍 Observation

Almost every string operation we need can be broken down into a few orthogonal concerns:

1. Where is the substring?

The number of choices is manageable:

the first "." (think of String.indexOf())
the last "/" (String.lastIndexOf())
the prefix "root/"
the suffix ".html"
a regular expression match

2. How do we navigate from the match?

Once we find it, we might want the:

part before it
part after it
substring up to the end of the match
substring from the match to the end of the string
the content between two patterns

3. Do we want a occurrence, or all?

Sometimes we just want the first. Other times, we want to find all occurrences.

4. What do we want to do with it?

Extract
Remove
Replace
Split around the occurrence (result in two parts)
Split around all occurrences (result in a stream or list)
Or just get the raw indices

📐 Step 1: The Substring as a Range

No matter how we find it, a substring is just a range: [begin, end). This is exactly how String.substring(int, int) works.

So let’s create a simple class to model it:

record Substring(String fullString, int begin, int end) {
  String before() { return fullString().substring(0, begin()); }

  String after() { return fullString().substring(end()); }

  String remove() { return before() + after(); }

  String replaceWith(String replacement) {
    return before() + replacement + after();
  }

  @Override String toString() {
    return fullString().substring(begin(), end());
  }
}

Already, we can add some trivial but useful before(), after(), remove(), and replaceWith() helpers.

Note: while the record looks extremely simple, it's the most important aspect of this design: all the extensibility and composability are centered around this simple concept: they are strategies to find, to navigate and to act on a range.

🧭 Step 2: Finding a Substring

We need an abstraction for “a way to find a Substring in a given input.” Let's call it Pattern:

interface Pattern {
    Optional<Substring> find(String input, int fromIndex);

    static Pattern first(String sub) {
      return (input, fromIndex) -> {
        int index = input.indexOf(sub, fromIndex);
        return index < 0
            ? Optional.empty()
            : Optional.of(new Substring(input, index, index + sub.length()));
      };
    }

    static Pattern last(String sub) {
      // almost same as first(), except use lastIndexOf()
    }

    static Pattern prefix(String s) {
      return (input, fromIndex) -> {
        return input.startsWith(s, fromIndex)
            ? Optional.of(new Substring(input, fromIndex, fromIndex + s.length()))
            : Optional.empty();
      };
    }

    static Pattern suffix(String s) {
      // very similar to prefix()
    }
}

That's it. The static methods such as first(), last(), prefix() etc. correspond to the first observation (where to find).

The find() method returns an Optional, and this design principle applies across the API: all substring extraction methods return Optional. This ensures that absence is explicit and must be handled consciously, avoiding the kind of implicit fallbacks or silent failures seen in methods like substringAfter() and substringBefore().

We also let the find() method take a secondary int fromIndex parameter to facilitate chaining, which you’ll see shortly.

🧭 Step 3: Using the Found Substring

As we've seen, there are many things we might want to do once we've found a substring.

The Substring record provides the index and some basic helper methods like remove() and replaceWith(). But we can also add higher-level methods to Pattern to directly perform common operations like extraction, removal, replacement, and splitting—without requiring the caller to explicitly invoke find().

    default Optional<String> from(String input) {
      return find(input, 0).map(Substring::toString);
    }

    default String removeFrom(String input) {
      return find(input, 0).map(Substring::remove).orElse(input);
    }

    default String replaceFrom(String input, String replacement) {
      return find(input, 0)
          .map(sub -> sub.replaceWith(replacement))
          .orElse(input);
    }

    default <T> Optional<T> split(
      String input, BiFunction<String, String, T> fn) {
        return find(input, 0)
          .map(sub -> fn.apply(sub.before(), sub.after()));
    }

These helpers let us perform removal, replacement, and splitting on any of the first(), last(), prefix(), or suffix() patterns in a consistent and predictable way.

The return value of from() is Optional to force the caller to explicitly handle missing matches—avoiding assumptions like those made by substringAfter().

The removeFrom() and replaceFrom() methods don’t return Optional because, idiomatically, removal is a no-op if the pattern isn’t found (just like Collection.remove()).

🧭 Step 4: Composition and Navigation

We’re still missing an important part of the API: how to express operations like before(first(foo)), after(last(bar)), or between(a, b).

We can build this via composition. This is also where the int fromIndex parameter to find() becomes useful:

    static Pattern before(Pattern p) {
      return (input, fromIndex) -> p.find(input, fromIndex)
          .map(sub -> new Substring(input, fromIndex, sub.begin()));
    }
    static Pattern after(Pattern p) {
      return (input, fromIndex) -> p.find(input, fromIndex)
          .map(sub -> new Substring(input, sub.end(), input.length()));
    }

    static Pattern between(Pattern a, Pattern b) {
        return (input, fromIndex) -> {
          return a.find(input, fromIndex)
              .flatMap(left ->
                  b.find(input, left.end())
                      .map(right ->
                          new Substring(input, left.end(), right.begin())
                      ));
        };
    }

    static Pattern between(String a, String b) {
        return between(first(a), first(b));
    }

The before(p) pattern applies p and returns everything to the left; after(p) returns everything to the right.

The between(a, b) pattern first applies a, then applies b starting from the end of a.

You can use the same strategy to build other navigational patterns like upToIncluding(...).

The overload between(String, String) is just a convenience method for common cases like between("(", ")").

✅ How Are We Doing?

Let’s revisit the Part 1 use cases.

We can now express many earlier problems using simple, composable code:

Extracting the extension name:

String ext = after(last(".")).from("myfile").orElse("");

Unlike substringAfter(), the fallback logic is explicit—no room for error.

Getting the directory:

String dir = before(last('/')).from("myfile").orElse(""); // → ""

Again, it forces you to be explicit—you cannot forget.

Getting directory path between root and last "/":

Pattern path = between(prefix("home/usr/"), last("/"));
String result = path.from("home/usr/module/component/file.txt").orElse("");
     // → "module/component"

Split a key-value pair

Pattern eq = Pattern.first("=");
Optional<Pair<String, String>> kv = first("=").split("k1=v1", Pair::new);
// → Optional[Pair("k1", "v1")]

Optional<Pair<String, String>> failed = first("=").split("k1", Pair::new);
// → Optional.empty()

🔁 Step 5: Repeating Pattern

Sometimes we want to apply the same pattern repeatedly. That’s where RepeatingPattern comes in:

record RepeatingPattern(Pattern base) {
  List<Substring> findAll(String input) {
    List<Substring> result = new ArrayList<>();
    int start = 0;
    while (true) {
      Substring sub = base().find(input, start).orElse(null);
      if (sub == null) break;
      result.add(sub);
      start = sub.end();
    }
    return result;
  }

  String replaceAllFrom(String input, String replacement) {
    StringBuilder result = new StringBuilder();
    int cursor = 0;
    for (Substring sub : findAll(input)) {
      result.append(input, cursor, sub.begin());
      result.append(replacement);
      cursor = sub.end();
    }
    result.append(input.substring(cursor));
    return result.toString();
  }

  String removeAllFrom(String input) {
    return replaceAllFrom(input, "");
  }

  List<String> split(String input) {...}
}

With pretty straightforward implementation code, we've added useful "acting" functionalities for all the previously defined substring patterns.

You can also implement the n-way split() using the results from findAll(). We omit it here for brevity.

For ergonomic chaining, let’s add a repeatedly() helper to Pattern:

  RepeatingPattern repeatedly() { return new RepeatingPattern(this); }

✅ What Have We Accomplished?

We've built a library with pretty simple API, yet with sufficient flexibility to cover diverse everyday String use cases.

This is possible because we've decoupled orthogonal concerns:

first(), last(), prefix(), suffix() and friends do one thing only: find the range.
before(), after(), between(), upToIncluding(), toEnd() do one thing only: compose from simpler patterns to more sophisticated patterns.
.from(String), .split(String), .replaceFrom(String) etc. do one thing only: given any simple or composite pattern, perform extraction, splitting, replacing from the range.
.repeatedly() turns any pattern into a RepeatingPattern, and then provide operations on all occurrences of a pattern.

Each individual family of methods are relatively straightforward, but combined together, they can perform far more sophisticated string operation.

Below, let's take a look at how we can use a combination to solve a more complex problem.

Split multiple key-values from a structured map string

This example shows how to compose Pattern and RepeatingPattern to achieve a relatively complex task:

String input = "{k1=v1, k2=v2, k3=v3}";
String content = Pattern.between("{", "}").from(input).orElseThrow();

Map<String, String> result = first(",").repeatedly()
    .split(content)
    .stream()
    .map(entry -> Pattern.first("=").split(entry.trim(), Map::entry).orElseThrow())
    .collect(Collectors.toMap(Entry::getKey, Entry::getValue));

// → {k1=v1, k2=v2, k3=v3}

Here’s what’s happening:

We use between("{", "}") to extract the content.
Then we split it into key-value strings using first(",").repeatedly().
Finally, each key-value string is split again by = into a Map.Entry.

This API lets you build robust and extremely flexible string manipulation logic without worrying about magic offsets, nulls, or off-by-one errors—all with predictable failure behavior.

We've covered the basics of the Substring API design.

The actual library is extensively used in Google's internal codebase and includes many more features such as look-around support (.immediatelyBetween(...), followedBy(...), etc.).

Check out Git Repo.

Designing a Better String Utility - Part 1

Dash One — Wed, 18 Jun 2025 16:20:36 +0000

Simple Things Not Easy

Finding a substring is the most basic text operation in any language. And yet in Java, even Kotlin, is surprisingly awkward and error-prone.

Consider the following example that finds the extension name of a file:

val ext = "myfile".substringAfter(".")

The file actually has no extension name, but the code returns myfile.

That's odd?!

You could explicitly choose a different default behavior. But that's the point:, the default behavior is confusing and it will bite you!

What makes things worse, is if you are used to Apache's StringUtils, you may have expected differently:

String ext = StringUtils.substringAfter("myfile", ".");

Now it says the extension name is empty. Seems to make more sense?

So, should Kotlin's String API have followed StringUtils?

Not quite. Let's study the following StringUtils example:

🔥 Extracting the Directory Path

String directory = StringUtils.substringBeforeLast(filename, "/");

If filename is "path/to/file", the code will extract "path/to" as the directory.

But what happens if filename is merely "myfile"? Interestingly, StringUtils decides to use a different strategy for the "not found" case: to fall back to the original string, which is "myfile".

But "myfile" is not the directory path!

At least Kotlin is consistent with itself to always fall back to the original string:

val directory = filename.substringBeforeLast("/") // → "myfile"

When we call an extraction method, we're asking for something specific. If the thing doesn't exist, quietly pretending it does is misleading—and confusing.

Worse, the fallback behavior is inconsistent across methods:

substringBefore() → returns the original string
substringAfter() → returns an empty string
substringBetween() → returns null

Same type of failure. Three different, silent error results.

🔥 Extracting Path Under Root

Given file path "home/usr/path/to/file.txt", we want to extract the "path/to" part after the known "home/usr/" prefix:

Kotlin:

val directory =
    path.removePrefix("home/usr/").substringBeforeLast("/")

Apache Commons:

String directory = StringUtils.substringBeforeLast(
    StringUtils.removeStart(path, "root/"),
    "/");

Again, the happy path seems fine. But what happens if path doesn't start with /home/usr/? Or if it doesn't have another / after the prefix? Say, it's just myfile?

As discussed earlier, the "path under root" then becomes "myfile". Not intuitive, and readers will likely need to look up the document to tell.

Let's look at a few other real world use cases.

🔥 Splitting a Key-Value Pair

Given the following HTTP line:

String line = "Authorization: Bearer token";

How do you get the header name and value?

Kotlin:

val parts = line.split(":", limit = 2)
val key = parts[0]          // → "Authorization"
val value = parts.getOrNull(1)?.trim() ?: ""  // → "Bearer token"

Apache Commons:

String[] parts = StringUtils.split(line, ":", 2);
String key = parts.length > 0 ? parts[0] : "";           // → "Authorization"
String value = parts.length > 1 ? parts[1].trim() : "";  // → "Bearer token"

Note that if you don't carefully check the result array's length, you will run into exceptions when the input string doesn't include the colon (:) character.

🔥 Parsing Multiple Key-Value Pairs

What if I want to parse a dictionary-like input string such as the following?

String input = "{k1=v1, k2=v2, k3=kv}";

Kotlin:

val raw = input.removeSurrounding("{", "}")
val map = raw.split(",").mapNotNull {
    val kv = it.split("=", limit = 2)
    if (kv.size == 2) kv[0].trim() to kv[1].trim() else null
}.toMap()

Apache Commons:

String trimmed = StringUtils.removeStart(input, "{");
trimmed = StringUtils.removeEnd(trimmed, "}");
String[] entries = StringUtils.split(trimmed, ",");
Map<String, String> map = new LinkedHashMap<>();
for (String entry : entries) {
    String[] kv = StringUtils.split(entry, "=");
    if (kv.length == 2) {
        map.put(StringUtils.trim(kv[0]), StringUtils.trim(kv[1]));
    }
}

Neither the Kotlin code or the Apache StringUtils code is convenient or easy to read.

Why Is It So Hard?

1. Error Handling

One-off util methods tend to be arbitrary in their error handling strategy, as discussed above.

It's tempting to pick a seemingly okay default value in order to keep the method signature "simple", at the cost of potential confusions.

And with arbitrary choice of default values, it can easily get inconsistent, making it even harder for people to remember.

2. One Method Per Use Case? That Doesn’t Scale

Every real-world string task feels slightly different.

But writing a separate method for each case quickly gets out of hand.

That’s why Apache Commons StringUtils has over 200 public static methods, including:

splitByWholeSeparatorPreserveAllTokens(...)
splitByCharacterTypeCamelCase(...)

These method names are overly long, to the point that you might not be able to intuitively get what they do. They are narrowly scoped to a specific use case that you have to carefully read the javadoc to understand.

They are rarely composable and their edge cases can sometimes be surprising.

3. The Static Util Class Trap

StringUtils mixes up two separate concerns:

How to find something in a string
What to do with it once found

Instead of composition, you get a mess of methods with long names and adhoc behavior. It's why util classes are often considered an anti-pattern.

What we really need is a way to model finding and acting separately.

In Part 2, we’ll try to build around a simple abstraction. And we'll see if a different approach can result in better coverage, with a simpler API.

The Easiest String Parsing in Java

Dash One — Wed, 21 May 2025 14:37:39 +0000

Parsing structured strings in Java has always been painful. Most developers reach for regular expressions, split(), or manual slicing. But these techniques are error-prone, hard to read, and most importantly—unsafe at compile time.

The StringFormat class makes parsing so easy that even a beginner can implement with a one-liner.

🧩 Regex is Not Easy

Take a common use case: parsing a file path like this:

/logs/2024/05/16/system.log

You want to extract year, month, day, and filename. Here’s what most people do:

private static final Pattern LOG_PATH = Pattern.compile(
    "/logs/(\\d{4})/(\\d{2})/(\\d{2})/(.+)\\.log"
);

// elsewhere in code:
Matcher matcher = LOG_PATH.matcher(path);
if (matcher.matches()) {
    String year = matcher.group(1);
    String month = matcher.group(2);
    String day = matcher.group(3);
    String file = matcher.group(4);
}

Some problems:

Regex pattern readability sucks.
Use group names and your pattern readability sucks even more.
With pattern and extraction logic far apart, you could get the groups out of order.
Group indices are magic numbers.

✅ Structured Parsing with StringFormat

Tthe same logic using StringFormat:

private static final StringFormat FORMAT =
    new StringFormat("/logs/{year}/{month}/{day}/{file}.log");

FORMAT.parseOrThrow(
    "/logs/2024/05/16/system.log",
    (year, month, day, file) ->
        new Log(parseInt(year), parseInt(month), parseInt(day), file);

That’s it. No string math, no group numbers.

🛡️ Compile-time Safety

StringFormat performs compile-time validation of the lambda:

// ❌ Error: parameter count mismatch
new StringFormat("{a}-{b}")
    .parseOrThrow("1-2", (a, b, c) -> { });
//                       ~~~~~~~~~~~~~~~
//                       Compilation error: too many parameters

// ❌ Error: parameter order mismatch
new StringFormat("{a}-{b}")
    .parseOrThrow("1-2", (b, a) -> { });
//                       ~~~~~~~
//                       Compilation error: expected order (a, b)

// ✅ Correct: order matches field declaration
new StringFormat("{a}-{b}")
    .parseOrThrow("1-2", (a, b) -> ...);

This level of safety is not possible with regex, split(), or ad-hoc parsing.

No need to “remember” group indices or keep documentation in sync with code—the compiler checks it for you.

✅ Scanning repeatedly

Say, if you have many such file paths in the input string, you can lazily scan them all:

List<Log> logs = FORMAT.scan(input, (year, month, day, file) -> ...)
    .filter(...)  // apply whatever filtering you care about
    .limit(10)    // if you want up to 10 such files
    .toList();

✅ Regex is Unpredictable

Regex engines in Java (and many other platforms) use NFA-based backtracking, which means certain patterns (especially involving nested repetitions or ambiguous alternations) can cause catastrophic slowdowns.

Even simple-looking regexes like:

href="([^"]*)"

or:

((a|b|c)+)+

can trigger catastrophic backtracking when matched against malicious input like nested quotes or repeated characters. These aren’t toy examples—real-world systems have gone down because of them:

Stack Overflow 2016: a regex used to extract comment anchors caused a global outage due to backtracking explosion (postmortem).
Cloudflare 2019: a single WAF rule with a pathological regex caused CPU saturation and took down large parts of the network (incident report).

RE2, Google's safe regex engine, avoids this with DFA-based guarantees—but at the cost of expressive power (e.g., no backreferences or lookaround) and often slower than hand-written substring logic.

✅ StringFormat uses `indexOf()` calls

StringFormat avoids regex entirely. It splits the template into static fragments and uses a left-to-right scan driven by String.indexOf(...) to locate placeholder matches.

This gives several benefits:

✅ Deterministic linear scanning
✅ No backtracking
✅ No regex syntax or escaping
✅ Fast constant-time fragment matching (in practice, indexOf(...) is extremely fast for short needles)
✅ Safe under adversarial input (no regex ReDoS risk)

In real workloads, where fragments are small (/, :, @, etc.) and inputs are well-structured, indexOf() outperforms regex by a wide margin—often many times faster per match.

🧠 Summary

If you're building tooling that parses structured text:

Don't use regex unless you need full pattern generality.
Don’t trust that it will behave the same under scale or attack.
Use simple substring matching where structure allows—like StringFormat does.

↔️ Bidirectional

While parsing is the main use case, the same format string also supports formatting:

String path = FORMAT.format(year, month, day, file);

The format string is always the source of truth. No string concatenation. No misplaced .append() chains.

Similar compile-time protection exists: you'll get compilation error if you pass in wrong number of args, or for example get the file and year/month/day in the wrong order.

With traditional String.format("input size for %s is %s", user.id(), input.size()), it's not a good idea to stash away the format string as a constant because then it's easy to pass the format arguments in the wrong order.

But with StringFormat and its compile-time check, it's safe to do so, making it easier to reuse the same format string at different places.

format() uses direct string concatenation (+), which is faster than StringBuilder on Java 9 and higher.

🐍 Python's `parse`

Looking around, Python offers similar syntax in its parse library:

from parse import parse

result = parse("/logs/{year}/{month}/{day}/{file}.log", "/logs/2024/05/17/server.log")
print(result.named)  # {'year': '2024', 'month': '05', 'day': '17', 'file': 'server'}

Except parse() offers no compile-time enforcements, and under the hood is a wrapper of regex, so suffers the same NFA-based regex performance overhead and potential disastrous backtracking.

🌍 Other Languages

Language	Closest Equivalent	Readability	Compile-Time Safety	Bidirectional	Notes
Java	`StringFormat`	✅ High	✅ Yes	✅ Yes	Template-based parsing with lambda + type safety
Python	`parse`	✅ High	❌ No	✅ Yes	Clean syntax, runtime-only verification
JS/TS	`path-to-regexp`, `match()`	⚠️ Medium	❌ No	⚠️ Partial	URL-focused, lacks general structure matching
Go	`regexp` (manual group extraction)	❌ Low	❌ No	❌ No	Verbose and error-prone, no field names
C++	`std::regex`, manual parsing	❌ Low	❌ No	❌ No	No built-in structure mapping; verbose
Kotlin	`Regex`, manual destructuring	⚠️ Medium	❌ No	❌ No	No declarative templates, no type checks

🔍 Observations

Python is the only language with syntax on par with StringFormat, but all verification is deferred to runtime.
JavaScript, Go, C++, and Kotlin rely on regex or ad-hoc logic without structural templates.
Only Java + StringFormat delivers template-based parsing with lambda field binding, and compiler-checked safety.

👉 Github Repo: Mug

Off-by-1 again in your LeetCode binary search solution?

Dash One — Fri, 16 May 2025 04:11:25 +0000

“Although the basic idea of binary search is straightforward, the details are surprisingly tricky...

In fact, binary search has been incorrectly implemented in textbooks, published code, and production software for decades.”

— Donald Knuth, The Art of Computer Programming, Vol. 3

“The truth is, very few correct versions have ever been published, at least in mainstream programming languages.”

— Joshua Bloch, Google Research Blog (2006)

Binary search is a beautiful algorithm — but implementing it is full of sharp edges:

off-by-one errors
lo <= hi or lo < hi?
hi = mid or hi = mid - 1?
mid overflow
loop doesn't stop

The BinarySearch class helps to abstract away those nuances.

🧠 How it Works

You provide a lambda that tells the algorithm which direction to search. Just return:

-1 → search left
1 → search right
0 → stop (target found)

It follows the same contract as Comparator.

BinarySearch.forInts(Range.closed(min, max))
    .insertionPointFor((lo, mid, hi) -> ...)
    .floor(); // or .ceiling()

⬇️ floor() or ⬆️ ceiling()?

Once the search lands on an insertion point, you choose:

.floor() → the last value that will drive the lambda to search up or stop. e.g., last i where nums[i] <= target
.ceiling() → the first value that will drive the lambda to search down or stop. e.g., first i where nums[i] >= target

🍌 LeetCode 875: Koko Eating Bananas

int minSpeed(List<Integer> piles, int h) {
  return BinarySearch.forInts(Range.closed(1, max(piles)))
      // if Koko can finish, eat slower, else eat faster
      .insertionPointFor(
          (lo, speed, hi) -> canFinish(piles, speed, h) ? -1 : 1)
      // ceiling() is the first value that canFinish()
      .ceiling();
}

🧮 LeetCode 69: Integer Square Root

int mySqrt(int x) {
  return BinarySearch.forInts(Range.closed(0, x))
      // if square is larger, try smaller sqrt
      .insertionPointFor(
          (lo, mid, hi) -> Long.compare(x, (long) mid * mid))
      // floor() is the max whose square <= x
      .floor();
}

📦 LeetCode 410: Split Array Largest Sum

int splitArray(int[] nums, int k) {
  int total = Arrays.stream(nums).sum();
  int max = Arrays.stream(nums).max().getAsInt();
  return BinarySearch.forInts(Range.closed(max, total))
      // if canSplit, try smaller sum, else try larger sum
      .insertionPointFor(
          (lo, maxSum, hi) -> canSplit(nums, maxSum, k) ? -1 : 1)
      // ceiling is the min sum that can split
      .ceiling();
}

🔍 TL;DR: Logic Summary

Problem	Search Domain	Predicate	Result
Eating bananas	`forInts`	`canFinish(speed) ? -1 : 1`	`.ceiling()`
Square root	`forInts`	`compare(x, mid²)`	`.floor()`
Split array	`forInts`	`canSplit(sum) ? -1 : 1`	`.ceiling()`

🤔 Can I Use it on LeetCode?

Not directly. LeetCode doesn’t support third-party libraries.

But you can use it to:

Quickly prototype and verify your binary search algorithm.
Divide and conquer. Avoid wrestling with bugs and boilerplate until you know your canSplit(), canFinish() logic works.

📦 More LeetCode binary search algorithms
📦 GitHub repo

Iteration - Generate Stream Recursively

Dash One — Sun, 23 Jun 2024 23:54:23 +0000

The Iterators

For anyone having been in programming a couple of years, chances are you've run into an interview question or an assignment like iterator for binary tree.

There are variations like for the "pre-order", "post-order" or "in-order" traversal; or sometimes you got a n-ary tree instead of a bnary tree.

A reason this kind of questions are used in interviews is because they require some meticulous bookkeeping, and there are loads of edge cases to bite you if you aren't careful.

Fine, it's 2024 and we have Stream now. How about having some fun and creating an infinite stream to generate the Fibonacci sequence?

The one thing in common? They are all boringly painful to write and read. Playing with them for the interview is cool; but having to read them in real life is no fun.

Recursion is easy

Imagine you are writing in-order traversal the most naive way:

void traverseInOrder(Tree tree) {
  if (tree.left != null) traverseInOrder(tree.left);
  System.out.println(tree.value);
  if (tree.right != null) traverseInOrder(tree.right);
}

void fibonacci(int a, int b) {
  System.out.println(a);
  fibonacci(b, a + b);
}

fibonacci(0, 1);

Except the hardcoding of System.out.println(), and never mind the stack overflow caused by the infinite recursion, at least it's easy, right?

Why can't we have some meat - scratch that - why can't we keep the simplicity and just fix the hardcoding and the stack overflow?

Design the API

This is my favorite part: to dream about what I would really really want, if everything just magically works.

Let's see... I don't want the hardcoding, so maybe this?

void traverseInOrder(Tree tree) {
  if (tree.left != null) traverseInOrder(tree.left);
  generate(tree.value);
  if (tree.right != null) traverseInOrder(tree.right);
}

void fibonacci(int a, int b) {
  generate(a);
  fibonacci(b, a + b);
}

fibonacci(0, 1);

The imagined generate() call will put the elements in the final stream.

It doesn't solve the stack overflow though.

The very nature of an infinite stream means that it has to be lazy. The caller could decide to use .limit(50) to only print the first 50 numbers and the recursive call shouldn't progress beyond the first 50 numbers.

So I need something that delays the recursion call. The idiomatic way in Java to model laziness is to wrap it in a callback interface. So let's create one:

interface Continuation {
  void evaluate();
}

And then I need a method similar to the generate() call but accepts a Continuation. The syntax should look like:

void traverseInOrder(Tree tree) {
  if (tree.left != null) {
    yield(() -> traverseInOrder(tree.left));
  }
  generate(tree.value);
  if (tree.right != null) {
    yield(() -> traverseInOrder(tree.right));
  }
}

I stole the yield keyword from other languages like C# with native generator support (it means to yield control to the runtime and also yield the evaluation result into the stream). Recent Java versions have made it a reserved word so you'll likely need to call it using this.yield() instead.

By wrapping the recursive call in a lambda passed to yield(), I should get the effect of lazy evaluation. The implementation's job will be to ensure the right order between the directly generated elements and the lazily generated ones.

In summary, the draft API we have come up with so far:

class Iteration<T> {
  void generate(T element);
  void yield(Continuation continuation);

  /** Turns the Iteration into a stream */
  Stream<T> iterate();
}

In case it wasn't obvious, we need the iterate() method to package it all up as a lazy stream.

The final syntax we want:

class InOrderTraversal<T> extends Iteration<T> {
  InOrderTraversal<T> traverseInOrder(Tree tree) {
    if (tree.left != null) {
      this.yield(() -> traverseInOrder(tree.left));
    }
    generate(tree.value);
    if (tree.right != null) {
      this.yield(() -> traverseInOrder(tree.right));
    }
    return this;
  }
}
Stream<T> stream =
    new InOrderTraversal<T>().traverseInOrder(tree).iterate();

class Fibonacci extends Iteration<Integer> {
  Fibonacci startFrom(int a, int b) {
    generate(a);
    this.yield(() -> startFrom(b, a + b));
    return this;
  }
}

Stream<Integer> stream =
    new Fibonacci().startFrom(0, 1).iterate();

Making it

It's nice to have a dream once in a while. We'll be able to use such API to turn many recursive algorithms trivially into lazy streams.

But aside from polishing up an API surface I like, there is nothing in concrete. How do I make it actually work?

First of all, if the thing only needs to handle generate(), it'd be a pointlessly trivial wrapper around a Queue<T>.

But we need to handle yield() with its lazy evaluation. Imagine we are effectively running this sequence:

generate(1);
generate(2);
yield(() -> {  // line 3
  generate(3);
  generate(4);
});
generate(5); // line 7

At line 3, can we enqueue the Continuation into the same queue before moving on to line 7?

If I do so, after line 7, the queue will look like [1, 2, Continuation, 5].

Now if we call iterate() and start to consume elements from the stream, 1 and 2 will be popped out, and then the Continuation object, with the number 5 still remaining in the queue.

Once the Continuation object is consumed, it needs to be evaluated, which will in turn generate 3 and 4. The question is where to put the two numbers?

We can't keep enqueueing them after the number 5 because it'll be out of order; we can't treat the queue as a stack and push them in FILO order because then we'll get [4, 3, 5].

Stack or Queue?

There are several ways to go about this.

One possibility is to create a stack of queues, where each time a Continuation is to be evaluated, push a new queue onto the stack. The stream will always consume elements from the top queue of the stack.

The downside is that you might end up creating and discarding many instances of ArrayDeque, which can be wasteful.

With some micro-optimization in mind, another approach is to use the two-stacks-as-a-queue trick.

The are two stacks: the inbox for writing and outbox for reading. When either generate() or yield() is called, we push into the
inbox stack; when the stream tries to consume, it flushes everything out of inbox into the outbox and then consumes one-by-one from the outbox.

To put it in context, upon seeing [Continuation, 5] in the outbox, the Continuation is evaluated, which puts [4, 3] in the inbox stack.

On the other side, the stream tries to consume. It pops and pushes [4, 3] onto the outbox stack, resulting in [3, 4, 5].

Implmentation-wise, we get to allocate no more than two ArrayDeques.

public class Iteration<T> {
  private final Deque<Object> outbox = new ArrayDeque<>();
  private final Deque<Object> inbox = new ArrayDeque<>(8);

  public final <T> void generate(T element) {
    if (element instanceof Continuation) {
      throw new IllegalArgumentException("Do not stream Continuation objects");
    }
    inbox.push(element);
  }

  public final void yield(Continuation continuation) {
    inbox.push(continuation);
  }

  private T consumeNextOrNull() {
    for (; ; ) {
      Object top = poll();
      if (top instanceof Continuation) {
        ((Continuation) top).evaluate();
      } else {
        return (T) top;
      }
    }
  }

  private Object poll() {
    Object top = inbox.poll();
    if (top == null) {  // nothing in inbox
      return outbox.poll();
    }
    // flush inbox -> outbox
    for (Object second = inbox.poll();
         second != null;
         second = inbox.poll()) {
      outbox.push(top);
      top = second;
    }
    return top;
  }
}

The poll() private method does the "flush inbox into outbox" logic mentioned above.

The consumeNextOrNull() method consumes the next element from the two-stack-queue, and evaluates Continuation when it sees one.

Wrap it all up

If you are with me so far, all we are missing is the iterate() method that wraps it all up as a Stream.

I'll cheat by just using Mug's whileNotNull() convenience method. But it's not hard to create your own by implementing a Spliterator.

public Stream<T> iterate() {
  return MoreStreams.whileNotNull(this::consumeNextOrNull);
}

And with that, our little generic recursive stream generator is complete.

Use it for real

Before we call it the day, let's see if we can use it to solve a more realistic problem.

Say, you are calling a ListAssets API that supports pagination. Request and response definitions are:

ListAssetsRequest {
  string userId;
  int page_size;
  string page_token;  // start from this page
}

ListAssetsResponse {
  List<Asset> assets;
  string next_page_token;  // empty if no more
}

If we were to naively fetch all pages and print them, it'll be as simple as sending request over and over again until the response.next_page_token is empty:

void showAllAssets(String userId) {
  ListAssetsRequest.Builder request =
      ListAssetsRequest.newBuilder().setUserId(userId);
  for (; ;) {
    var response = assetsApi.listAssets(request.build());
    for (Asset asset : response.getAssets()) {
      System.out.println(asset);
    }
    if (response.getNextPageToken().isEmpty()) {
      return;  // no more pages
    }
    request.setPageToken(response.getNextPageToken());
  }
}

But we can do better! Let's wrap it up as a lazy Stream<Asset> to give callers more flexibility. For example they can consume any number of assets and stop when needed without over-fetching pages unnecessarily.

Stream<Asset> listAssets(String userId) {
  class Pagination extends Iteration<ListAssetsResponse> {
    Pagination startFrom(String pageToken) {
      var response = assetsApi.listAssets(
          ListAssetsRequest.newBuilder()
              .setUserId(userId)
              .setPageSize(100)
              .setPageToken(pageToken)
              .build());
      generate(response);
      if (!response.getNextPageToken().isEmpty()) {
        this.yield(() -> startFrom(response.getNextPageToken()));
      }
      return this;
    }
  }
  return new Pagination().startFrom("").iterate()
      .flatMap(response -> response.getAssets().stream());
}

I trust you can read it alright, my friend. :)

Chain - a Goofy, Immutable List to Concatenate Millions

Dash One — Wed, 12 Jun 2024 05:04:14 +0000

What?

Java has array-based Lists for efficient random access; there are LinkedList for efficient appending.

But there is none that you can concatenate a million times for cheap.

Once upon a time

Agent Aragorn (Son of Arathorn), Jonny English and Smith collaborated on a bunch of missions.

The Mission class's signature is like:

abstract class Mission {
  abstract MissionId id();
  abstract Range<LocalDate> timeWindow();
  abstract ImmutableSet<Agent> agents();
}

The goal is to create an ImmutableRangeMap<LocalDate, Set<Agent>> (RangeMap is a Guava collection that maps disjoint ranges to values) to account for all the agents during each time window. Note that missions can have overlapping time windows, and agents could work on multiple missions at the same time.

So for missions like:

missions = [{
  timeWindow: [10/01..10/30]
  agents: [Aragorn, English]
}, {
  timeWindow: [10/15..11/15]
  agents: [Aragorn, Smith]
}]

I want the result to be:

[10/01..10/15): [Aragorn, English]
[10/15..10/30]: [Aragorn, English, Smith]
(10/30..11/15]: [Aragorn, Smith]

At first I thought to use the toImmutableRangeMap() collector, as in:

missions.stream()
    .collect(toImmutableRangeMap(Mission::timeWindow, Mission::agents));

Voila, done, right?

Not quite. My colleague pointed out that toImmutableRangeMap() does not allow overlapping ranges. It wants all input time windows to be disjoint.

`RangeMap` can `merge()`

The TreeRangeMap class has a merge() method that already does the heavylifting: finds overlappings and splits the ranges, and then merges the values mapped to the overlapping subrange.

With some effort, I created a toImmutableRangeMap(merger) BiCollector on top of the merge() function.

So if what I needed is just to count the number of agents, I could have done:

import static com.google.mu.util.stream.BiStream.biStream;

ImmutableRangeMap<LocalDate, Integer> agentCounts =
    biStream(missions)
        .mapKeys(Mission::timeWindow)
        .mapValues(mission -> mission.agents().size())
        .collect(toImmutableRangeMap(Integer::sum));

(It'll double count the duplicate agents though)

Anyhoo, here goes the interesting part: how do I merge the Set<Agent>?

Quadratic runtime

I could use Guava's Sets.union():

import com.google.common.collect.Sets;

ImmutableRangeMap<LocalDate, ImmutableSet<Agent>> agentsTimeline =
    biStream(missions)
        .mapKeys(Mission::timeWindow)
        .mapValues(mission -> mission.agents())
        .collect(toImmutableRangeMap((set1, set2) -> Sets.union(set1, set2).immutableCopy()));

The gotcha is that each time merging happens, merging two original sets into one is O(n) where n is the number of agents from the two overlapping ranges. If we are unlucky, we can get into the situation where a time window is repetitively discovered to overlap with another time window, and we keep copying and copying over again. The time complexity is quadratic.

Stack overflow

Could I remove the .immutableCopy()? Sets.union() returns a view that takes constant time so we should be good?

Not really. We don't know how many times merging will happen, a Set can be unioned, then unioned again for unknown times. In the worst case, we'd create a union-of-union-of-union N levels deep. If N is a large number, we'll stack overflow when we try to access the final SetView!

The same will happen if for example I use Iterables.concat() or Stream.concat() (javadoc discusses this problem).

And in case it wasn't obvious, the merging cannot modify either of the two lists or sets, because they are still associated with the sub-range that doesn't overlap. So we need it to be immutable.

If I had one of the persistent collections in the dependencies, I might just use it (they offer O(logn) performance for concatenation but usually are close to constant time). But I don't. And it doesn't feel like worth it to pull in one of such libraries for a single use case.

Put it in a tree

I slept on this problem for about two days for an idea to come to me: can we use something like Haskell's List?

Tl;dr, Haskell's List is like LinkedList except it's immutable. So given a list of [2, 3], you can cons the number 1 onto the list to get a new instance of [1, 2, 3]. Under the hood it's as simple as creating a new object with the internal tail pointer pointing to the old [2, 3] list.

If I can do this, each time merging happens, I only need to pay O(1) cost. The resulting object is probably less efficient for random access than ArrayList or Guava's ImmutableList because of all the pointers and indirections. But that's okay. When the whole split-merge process is done, I can perform a final copy into ImmutableList, which is O(n).

The only problem? Haskell's cons only allows to add one element, while I have two List<Agent>s to concatenate (I can't cons every element from one of the lists, because then I'm getting back to quadratic).

To support concat(list1, list2), I decided to use a binary tree to represent the List's state:

private static final class Tree<T> {
  final T mid;
  @Nullable final Tree<T> left;  // null means empty
  @Nullable final Tree<T> right;  // null means empty

  Tree(Tree<T> left, T value, Tree<T> right) {...}
}

In the list, the elements in left show up first, followed by mid, then followed by the elements in right. In other words, an in-order traversal will give us back the list.

The key trick is to figure out how to concatenate two binary trees into one. Intuitively, I need to find the new "mid point" value, which can be either the left tree's last element, or the right tree's first element. Say, if I take the right tree's first element, then the new tree's left remains the old left, while the new tree's right would need to be the old right after removing the first element.

Wrap it up

Since the Tree is immutable, how do I remove any element at all? And in a binary tree, finding the first element takes up to O(n) time (it's not a balanced tree).

It turns out there's a law in computer science:

All problems in computer science can be solved by another level of indirection

In human language: if a problem can't be solved with one layer of indirection, add two :)

Here goes my second layer of indirection that handles the remove first element from an immutable list task:

public final class Chain<T> {
  private final T head;
  @Nullable private final Tree<T> tail;

  public static <T> Chain<T> of(T value) {
    return new Chain<>(value, null);
  }

  public static <T> Chain<T> concat(Chain<T> left, Chain<T> right) {
    T newHead = left.head;
    Tree<T> newTail = new Tree<>(left.tail, right.head, right.tail);
    return new Chain<T>(newHead, newTail);
  }
}

This is quite like Haskell's cons list, except the tail is a binary tree instead of another cons list.

Now because both left and right Chain already have the first element readily accessible, I can just take the right head as the new mid point to build the new tree, with the tail from left and the tail from right. This new Tree maintains the order invariant as in left.tail -> right.head -> right.tail. And of course the left's head becomes the new Chain head.

It takes a bit of brain gymnastics. But if you sit down and think for a minute, it's actually pretty straight forward.

This solves the O(1) concatenation. And the good thing is that, no matter how deep concat() is nested, the result is always one layer of Chain with a heap-allocated Tree object.

Now we just need to make sure when we iterate through the Chain, we take no more than O(n) time, and constant stack space.

Flattening tree back to `List`

My secret weapon is Walker.inBinaryTree() (but you can create your own - it's standard tree traversal stuff). It already does everything I needed:

O(n) time lazy in-order traversal.
Constant stack space.

Using it is pretty simple. First we add a stream() method to the Tree class:

private static final class Tree<T> {
  ...

  Stream<T> stream() {
    return Walker.<Tree<T>>inBinaryTree(t -> t.left, t -> t.right)
        .inOrderFrom(this)
        .map(t -> t.mid);
  }
}

The inOrderFrom() method returns a lazy stream, which will take at the worst case O(n) heap space and constant stack space.

Then we wrap and polish it up in our wrapper Chain class:

public final class Chain<T> {
  ...

  /**
   * Returns a <em>lazy</em> stream of the elements in this list.
   * The returned stream is lazy in that concatenated chains aren't consumed until the stream
   * reaches their elements.
   */
  public Stream<T> stream() {
    return tail == null
        ? Stream.of(head)
        : Stream.concat(Stream.of(head), tail.stream());
  }
}

With that, it gives me O(n) time read access to the tree and I can easily collect() it into an ImmutableList.

In the actual implementation, I also made Chain implements List to make it nicer to use, and used lazy initialization to pay the cost only once. But that's just some extra API makeup. The meat is all here.

What about Concatenating Strings?

If we didn't have an agent list, but a string, how would you go about concatenating the strings without quadratic cost?

You could adopt a similar tree technique. But you can probably just reuse Chain. For example, wrap your leaf-level strings as Chain<String> using Chain.of(string).

Then just keep concatenating the Chain<String> until at the very end, you can do:

String finalConcatenatedString =
    finalStringChain.stream().collect(joining(""))  // O(n)

In Conclusion

Chain is a simple immutable List implementation that you can append, concatenate millions of times.

A bit of googling shows that people have run into similar needs but I didn't find a similar implementation that handles both the O(1) concatenation time and stack overflow concern.

Parsing dates and time without pattern string in Java

Dash One — Mon, 29 Apr 2024 02:23:39 +0000

The other day I needed to parse some timestamp strings loaded from a file. It's for a test where I wanted to feed these timestamps as Instant to an object I'm trying test. These time strings are like 2023-12-05 17:51:00-08:00.

First thing I tried was to just parse it:

Instant time = Instant.parse(timeString);

Of course it throws, right? Looked like I had to roll up my sleeves and figure out the right DateTimeFormatter before being able to parse them.

I kinda remembered that for the date, it's yyyy-MM-dd (important to use the upper case MM); and for the time it's hh-mm-ss. But I had no idea how to specify the timezone offset part.

So I went to read the javadoc of DateTimeFormatter. In retrospect, if I were in the mood of learning the API for the purpose of learning, it must have been fine. But I was more like:

C'mon, I just need to parse some timestamp. Where is the quick example that matches the format?

Unfortunately the javadoc reads more like a RFC document, with no cheetsheet that could help me in a hurry.

After deciding to sit down, and take my time to learn it, I finally figured out. And by the way I was wrong, it's not hh-mm-ss but HH-mm-ss. Oh well.

End of story.

But I hated this kind of yak shaving. You need to put aside the immediate task you had in mind, and instead research the knowledge for a preliminary step.

A colleague told me that what I want is something Golang does. That is, they don't use cryptic format specifiers, but instead just use an example datetime string.

I was like "shut up and take my money!" because it's exactly what I need: I don't have the specifiers, but I do have an example date time string.

Learning a bit more though, Golang's use of the magical reference date gave me the pause: if I can't remember the format specifiers, can I remember the magic date? It turns out that reference time isn't really intuitive either:

01/02 03:04:05PM 06 -0700

That stikes me as a bit too cute:

What year is 01/02?
Why PM? While it looks like natural 1-2-3-4-5-6-7, in the time format I'm most familiar with, it'll actually be 15:04:05, not easy to remember at all.
Why -0700 but not +07:00?

And if it only takes the reference date, I can't just pass a random string to parse without myself having to translate it to the reference date with my own man power.

The burning question is: if I can read 2023-12-05 17:51:00-08:00 and understand exactly what time it is, no ambiguity, and without knowing a reference time or the format specifiers, why can't the computer? This is no rocket science or AlphaGo.

So I started to build a library to help me parse all common dates and time strings. It should be able to infer from the input what the format specifiers should be (supports timezone, weekday, even including formats like 11/30/2024), and then use that format specifier to parse the date or time for me:

// Directly parsing dates and time
Instant timestamp = DateTimeFormats.parseToInstant(
   "2023-12-05 17:51:00-08:00");
LocalDate date = DateTimeFormats.parseLocalDate(
   "2023-12-05");
ZonedDateTime zonedDateTime = DateTimeFormats.parseZonedDateTime(
   "2023-12-05 17:51:00-08:00");

// Infer the DateTimeFormatter
DateTimeFormatter format = DateTimeFormats.formatOf(
   "2023-12-05 17:51:00-08:00");

It was a fun little project to build. Using the Substring library as the basic building block, I mostly avoided having to use regex or fiddling with string indexes and off-by-1 errors.

I like that it allows me to use any example date and time, without having to remember anything at all.

Maybe it'll be useful to you too?

String Manipulation Tricks (Day 1)

Dash One — Fri, 19 Apr 2024 01:42:33 +0000

(First post. Don't know what to blog about. I'll start by recording some random coding thought whenever they occur to me and I happen to have time to write it down)

I've recently been thinking about Java string manipulation. Then I stumbled upon this string parsing code:

private static final Pattern THE_NUMBER =
    Pattern.compile("^\\s\\(([1-9][0-9]*)\\)$");

// Find the number from string with header.
// example: parseTheNumber("foo", "foo (123)") -> 123
//          parseTheNumber("foo", "bar (123)") -> empty
//          parseTheNumber("foo", "foo (str)") -> empty
Optional<Integer> parseTheNumber(String header, String string) {
  if (!string.startsWith(header)) {
    return Optional.empty();
  }
  Matcher matcher = THE_NUMBER.matcher(
      string.substring(header.length()));
  try {
    return matcher.matches()
        ? Optional.of(Integer.parseInt(matcher.group(1)))
        : Optional.empty();
  } catch (NumberFormatException e) {
    return Optional.empty();
  }
}

As a racist against Java Regex, I can't help wanting to try it out without regex (using Guava and Mug, my all-in-one toolbox).

import com.google.common.primitives.Ints;
import com.google.mu.util.StringFormat;

private static final StringFormat THE_NUMBER =
    new StringFormat("{type} ({num})");

Optional<Integer> parseTheNumber(String header, String string) {
  // StringFormat.parse() will return empty()
  //     if failed to parse, or if the lambda returns null
  return THE_NUMBER.parse(
      string,
      // Ints.tryParse() returns null if failed to parse
      (type, num) -> type.equals(header) ? Ints.tryParse(num) : null);
}

StringFormat performs well compared to Java regex. And to me it's more readable.

What do you think?

DEV Community: Dash One

Introducing SafeSql - Enforced Injection Safety

SQL Injection

Existing Mitigations

Hardening the SQL String

SQL Template With Escape Hatch

Java DSL

SafeSql

How Does SafeSql Prevent SQLi?

Dynamic IN Clauses with Collections

Conditional Query Fragments

Injecting Identifiers like Column or Table Names

Proper Escaping for LIKE Patterns

Query Composition and Parameter Isolation

Parameter Name and Order Checking

Type Safety

Summary

Designing a Better String Utility - Part 2

Part 2: Designing a Better String Utility

🔍 Observation

1. Where is the substring?

2. How do we navigate from the match?

3. Do we want a occurrence, or all?

4. What do we want to do with it?

📐 Step 1: The Substring as a Range

🧭 Step 2: Finding a Substring

🧭 Step 3: Using the Found Substring

🧭 Step 4: Composition and Navigation

✅ How Are We Doing?

Extracting the extension name:

Getting the directory:

Getting directory path between root and last "/":

Split a key-value pair

🔁 Step 5: Repeating Pattern

✅ What Have We Accomplished?

Split multiple key-values from a structured map string

Designing a Better String Utility - Part 1

Simple Things Not Easy

🔥 Extracting the Directory Path

🔥 Extracting Path Under Root

🔥 Splitting a Key-Value Pair

🔥 Parsing Multiple Key-Value Pairs

Why Is It So Hard?

1. Error Handling

2. One Method Per Use Case? That Doesn’t Scale

3. The Static Util Class Trap

The Easiest String Parsing in Java

🧩 Regex is Not Easy

✅ Structured Parsing with StringFormat

🛡️ Compile-time Safety

✅ Scanning repeatedly

✅ Regex is Unpredictable

✅ StringFormat uses indexOf() calls

🧠 Summary

↔️ Bidirectional

🐍 Python's parse

🌍 Other Languages

🔍 Observations

Off-by-1 again in your LeetCode binary search solution?

🧠 How it Works

⬇️ floor() or ⬆️ ceiling()?

🍌 LeetCode 875: Koko Eating Bananas

🧮 LeetCode 69: Integer Square Root

📦 LeetCode 410: Split Array Largest Sum

🔍 TL;DR: Logic Summary

🤔 Can I Use it on LeetCode?

Iteration - Generate Stream Recursively

The Iterators

Recursion is easy

Design the API

Making it

Stack or Queue?

Wrap it all up

Use it for real

Chain - a Goofy, Immutable List to Concatenate Millions

What?

Once upon a time

RangeMap can merge()

Quadratic runtime

Stack overflow

`SafeSql`

How Does `SafeSql` Prevent SQLi?

Dynamic `IN` Clauses with Collections

✅ StringFormat uses `indexOf()` calls

🐍 Python's `parse`

`RangeMap` can `merge()`

Flattening tree back to `List`