[enhancement] Add peephole optimizations to generated BDD code

[ysaito1001]

Optimizations involve

• Coalesce and ite functions should never show up in generated code.
• Add explicit peephole optimizations that prevent allocations for things like substrings.

For example, instead of

private boolean cond6() {
    return ("--x-s3".equals(RulesFunctions.coalesce(RulesFunctions.substring(params.bucket(), 0, 6, true), "")));
}

code generate this instead:

private boolean cond6() {
    return (params.bucket() != null && params.bucket().endsWith("--x-s3"));
}

[landonxjames]

Further notes from Dowling on how to do this (I didn't understand the mechanical transform happening between the first version of the condition and the second):

MethodCall  { name: "equals" }
  ├── source ── LiteralString { value: "--x-s3" }
  └── args[0] ─ FunctionCall { name: "coalesce" }
                ├── args[0] ─ FunctionCall { name: "substring" }
                │             ├── args[0] ─ VariableRef { var: Bucket }   ⟶ prints `params.bucket()`
                │             ├── args[1] ─ LiteralInt    { value: 0 }     (start)
                │             ├── args[2] ─ LiteralInt    { value: 6 }     (stop)
                │             └── args[3] ─ LiteralBool   { value: true }  (reverse)
                └── args[1] ─ LiteralString { value: "" }                  (coalesce default)

  Every operand the rewrite needs — start, stop, reverse, the literal, the bucket sub-tree — is a
  distinct, already-parsed node. Nothing needs to be evaluated or re-parsed.

  Pseudo-code for the optimization

  This is the peephole that runs when the visitor reaches a MethodCall node, before the default
  <source>.<name>(<args>) printing:

  # ── entry point: called for every MethodCall node ────────────────────────────
  function emitMethodCall(node, out):
      if node.name == "equals" and node.args.length == 1
         and tryEmitPrefixSuffix(node.source, node.args[0], out):
          return BOOLEAN                      # rewritten; skip default printing

      # ── default: reproduce  source.name(args...)
      emit(node.source, out)
      out.write("." + node.name + "(")
      emitCommaSeparated(node.args, out)
      out.write(")")
      return typeOf(node)


  # ── the rewrite: equals(substring(x,s,e,rev), LIT) -> startsWith/endsWith ─────
  function tryEmitPrefixSuffix(a, b, out):
      # 1. identify which operand is the string literal and which is the substring,
      #    trying both argument orders (literal may be receiver OR argument)
      (literal, sub) = (asStringLiteral(a), substringOf(b))
      if literal == null or sub == null:
          (literal, sub) = (asStringLiteral(b), substringOf(a))
      if literal == null or sub == null or sub.args.length != 4:
          return false                        # shape doesn't match → caller prints normally

      # 2. read the compile-time constants straight off the leaf nodes
      x       = sub.args[0]                    # the bucket sub-expression (a subtree)
  function tryEmitPrefixSuffix(a, b, out):
      # 1. identify which operand is the string literal and which is the substring,
      #    trying both argument orders (literal may be receiver OR argument)
      (literal, sub) = (asStringLiteral(a), substringOf(b))
      if literal == null or sub == null:
          (literal, sub) = (asStringLiteral(b), substringOf(a))
      if literal == null or sub == null or sub.args.length != 4:
          return false                        # shape doesn't match → caller prints normally

      # 2. read the compile-time constants straight off the leaf nodes
      x       = sub.args[0]                    # the bucket sub-expression (a subtree)
      if literal == null or sub == null or sub.args.length != 4:
          return false                        # shape doesn't match → caller prints normally

      # 2. read the compile-time constants straight off the leaf nodes
      x       = sub.args[0]                    # the bucket sub-expression (a subtree)
      start   = asInt(sub.args[1])
      stop    = asInt(sub.args[2])
      reverse = asBool(sub.args[3])
      if start == null or stop == null or reverse == null:
          return false                        # non-constant bounds → don't rewrite

      # 3. equivalence precondition: the compared window width must equal the literal.
      #    (substring(x,s,e,rev)==LIT is a fixed-width region test only when |LIT| == e-s)
      if literal.value.length != stop - start:
          return false

      # 4. emit the allocation-free in-place form. `emit(x)` recursively prints the
      #    bucket subtree (→ "params.bucket()"), reused 2–3 times.
      out.write("(")
      emit(x, out); out.write(" != null && "); emit(x, out)
      if reverse and start == 0:
          out.write(".endsWith(" + quote(literal.value) + ")")            # suffix
      else if reverse:
          out.write(".startsWith(" + quote(literal.value) + ", ")
          emit(x, out); out.write(".length() - " + stop + ")")            # mid, from end
      else:
          out.write(".startsWith(" + quote(literal.value) + ", " + start + ")")  # from front
      out.write(")")
      return true

  # ── tiny structural classifiers (all pure instanceof / field reads) ──────────
  function asStringLiteral(n):
      return n if n is LiteralString else null

  function substringOf(n):                     # unwrap coalesce(substring(...), _)
      if n is not FunctionCall: return null
      if n.name == "coalesce" and n.args.length == 2 and n.args[0] is FunctionCall:
          n = n.args[0]                         # peel the coalesce wrapper
      return n if (n is FunctionCall and n.name == "substring") else null

  function asInt(n):   return n.value if n is LiteralInt  else null
  function asBool(n):  return n.value if n is LiteralBool else null

  Trace on cond6

  - emitMethodCall: name is "equals", 1 arg → call tryEmitPrefixSuffix(LiteralString("--x-s3"), coalesce(...)).
  - Step 1: asStringLiteral(a) → "--x-s3"; substringOf(b) peels coalesce → substring(...). Matched.
  - Step 2: x = params.bucket() subtree, start=0, stop=6, reverse=true.
  - Step 3: "--x-s3".length == 6 == 6-0 ✓.
  - Step 4: reverse && start==0 → emit (params.bucket() != null && params.bucket().endsWith("--x-s3")).

  Result:
  return (params.bucket() != null && params.bucket().endsWith("--x-s3"));

You can also just literally look for: stringEquals(substring(x,s,e,rev), lit) as a "substring equals" pattern. Smithy-Java does this for it's bytecode and turns it into a single SUBSTRING_EQ opcode.

[landonxjames]

And while I have it up, this is what we generate for S3's condition 6 today which does have an unnecessary allocation with "".to_string().

6 => (|_diagnostic_collector: &mut crate::endpoint_lib::diagnostic::DiagnosticCollector| -> bool {
    let partition_resolver = &self.partition_resolver;
    (crate::endpoint_lib::coalesce::coalesce!(
        if let Some(inner) = crate::endpoint_lib::substring::substring(
            if let Some(param) = bucket { param } else { return false },
            0,
            6,
            true,
            _diagnostic_collector
        ) {
            inner
        } else {
            return false;
        },
        "".to_string()
    )) == ("--x-s3")