openlatch-client 0.3.3

//! Would-have structural validation (D-04 / D-18).
//!
//! A trim that removes older history can leave a `tool_result` in the retained
//! tail whose matching `tool_use` was in the removed region. Such a request would
//! be rejected by the provider (a 400: an orphaned `tool_result`), so the
//! would-have is **structurally invalid** — it could not have been sent, and its
//! (possibly positive) net must not be credited as a saving. The engine records
//! `skipped_invalid` for it.
//!
//! This validator only *inspects* the retained tail — it never builds the trimmed
//! body (observe-only). It is deterministic and network-free.
//!
//! ## L-0's validation is a different shape (D-28)
//!
//! [`history_trim_is_valid`] answers "would this removal orphan something". L-0
//! removes nothing, so that question does not apply to it; the question that
//! does is **"is the rewritten body the same request"**. The two validators
//! below answer it by *comparison* — original against rewritten — rather than
//! by re-deriving structural rules, which makes them total rather than a
//! checklist someone has to keep complete.
//!
//! In particular, `tool_use` / `tool_result` pairing and message role
//! alternation are **proven, not re-walked**: both mechanisms leave `messages`
//! byte-identical, and these validators assert that equality directly. Asserting
//! the stronger property is cheaper than the weaker one and cannot be
//! incomplete. If a future mechanism ever touches `messages`, this comment is
//! the marker that its own pairing validator must be written first — the
//! equality assertion will fail closed until it is.

use std::collections::HashSet;

use serde_json::Value;

/// Would a history trim that retains exactly `retained` be structurally valid?
///
/// Valid iff every `tool_use_id` referenced by a `tool_result` in the retained
/// tail is produced by a `tool_use` **also** in the retained tail. A referenced id
/// that is missing means its `tool_use` was in the removed region → orphaned →
/// invalid.
pub fn history_trim_is_valid(retained: &[Value]) -> bool {
    let produced = tool_use_ids(retained);
    for message in retained {
        for block in content_blocks(message) {
            if block_type(block) == Some("tool_result") {
                if let Some(id) = block.get("tool_use_id").and_then(Value::as_str) {
                    if !produced.contains(id) {
                        return false; // a tool_result whose tool_use was trimmed away
                    }
                }
            }
        }
    }
    true
}

/// Collect the ids of every `tool_use` block across `messages`.
fn tool_use_ids(messages: &[Value]) -> HashSet<&str> {
    let mut ids = HashSet::new();
    for message in messages {
        for block in content_blocks(message) {
            if block_type(block) == Some("tool_use") {
                if let Some(id) = block.get("id").and_then(Value::as_str) {
                    ids.insert(id);
                }
            }
        }
    }
    ids
}

/// The `content` blocks of a message, or an empty slice when `content` is a bare
/// string (a plain-text message carries no tool blocks).
fn content_blocks(message: &Value) -> &[Value] {
    message
        .get("content")
        .and_then(Value::as_array)
        .map(Vec::as_slice)
        .unwrap_or(&[])
}

/// A block's `type` discriminator (`tool_use`, `tool_result`, `text`, …).
fn block_type(block: &Value) -> Option<&str> {
    block.get("type").and_then(Value::as_str)
}

// ---------------------------------------------------------------------------
// L-0 structural validation (D-28). Comparison-based: original vs rewritten.
// ---------------------------------------------------------------------------

/// Is a `reorder_blocks` result the same request, differently ordered?
///
/// Valid iff **all** of:
///
/// - every top-level key other than `system` is byte-identical (so `model`,
///   `tools`, `messages`, `tool_choice`, `max_tokens` and everything else are
///   untouched — which is what proves tool pairing and role alternation intact);
/// - the same top-level keys are present, none added or dropped;
/// - `system` is an array in both, of the same length;
/// - `system` is a **permutation**: every block in the original appears in the
///   rewritten exactly as many times as it did, byte-identical, with nothing
///   added, dropped, edited or duplicated.
///
/// Multiset equality rather than set equality is deliberate: two identical
/// blocks are a legitimate prompt, and set equality would let a transform
/// silently drop one of them.
pub fn reorder_is_structurally_valid(original: &Value, rewritten: &Value) -> bool {
    if !non_system_keys_are_identical(original, rewritten) {
        return false;
    }
    let (Some(a), Some(b)) = (
        original.get("system").and_then(Value::as_array),
        rewritten.get("system").and_then(Value::as_array),
    ) else {
        return false;
    };
    is_permutation(a, b)
}

/// Is an `insert_breakpoints` result the same request with markers added?
///
/// Valid iff **all** of:
///
/// - every top-level key other than `system` is byte-identical;
/// - `system` is an array in both, of the same length, **in the same order**
///   (this mechanism moves nothing);
/// - each block differs from its original at most by the **addition** of a
///   `cache_control` key. No text is edited, no other key is added or removed,
///   and an existing `cache_control` is never rewritten — displacing one would
///   silently uncache whatever it covered (D-19).
pub fn insert_is_structurally_valid(original: &Value, rewritten: &Value) -> bool {
    if !non_system_keys_are_identical(original, rewritten) {
        return false;
    }
    let (Some(a), Some(b)) = (
        original.get("system").and_then(Value::as_array),
        rewritten.get("system").and_then(Value::as_array),
    ) else {
        return false;
    };
    a.len() == b.len()
        && a.iter()
            .zip(b.iter())
            .all(|(before, after)| differs_only_by_added_cache_control(before, after))
}

/// Do the two documents agree on every top-level key except `system`, and on
/// which keys exist at all?
fn non_system_keys_are_identical(original: &Value, rewritten: &Value) -> bool {
    let (Some(a), Some(b)) = (original.as_object(), rewritten.as_object()) else {
        return false;
    };
    if a.len() != b.len() {
        return false;
    }
    a.iter().all(|(k, v)| k == "system" || b.get(k) == Some(v))
        && b.keys().all(|k| a.contains_key(k))
}

/// Multiset equality over blocks — same members, same multiplicities.
///
/// `O(n²)` on the block count, which is correct here: `system` arrays are a
/// handful of blocks (bounded at 64 by the shape tracker), and a comparison
/// that needs no hashing cannot disagree with byte equality.
fn is_permutation(a: &[Value], b: &[Value]) -> bool {
    if a.len() != b.len() {
        return false;
    }
    let mut claimed = vec![false; b.len()];
    for block in a {
        match b
            .iter()
            .enumerate()
            .position(|(i, candidate)| !claimed[i] && candidate == block)
        {
            Some(i) => claimed[i] = true,
            None => return false,
        }
    }
    true
}

/// Is `after` exactly `before` plus (at most) a new `cache_control` key?
fn differs_only_by_added_cache_control(before: &Value, after: &Value) -> bool {
    let (Some(a), Some(b)) = (before.as_object(), after.as_object()) else {
        return before == after;
    };
    // Everything the original had must survive byte-identically, including an
    // existing `cache_control`.
    if !a.iter().all(|(k, v)| b.get(k) == Some(v)) {
        return false;
    }
    // The only key the rewritten may have gained is `cache_control`.
    b.keys().all(|k| a.contains_key(k) || k == "cache_control")
}

#[cfg(test)]
mod tests {
    use super::*;
    use serde_json::json;

    fn tool_use(id: &str) -> Value {
        json!({ "role": "assistant", "content": [ { "type": "tool_use", "id": id, "name": "search", "input": {} } ] })
    }

    fn tool_result(id: &str) -> Value {
        json!({ "role": "user", "content": [ { "type": "tool_result", "tool_use_id": id, "content": "ok" } ] })
    }

    #[test]
    fn matched_tool_pair_in_the_tail_is_valid() {
        let retained = vec![tool_use("toolu_1"), tool_result("toolu_1")];
        assert!(history_trim_is_valid(&retained));
    }

    #[test]
    fn orphaned_tool_result_is_invalid() {
        // The tool_use (toolu_9) is NOT in the retained tail — it was trimmed away,
        // leaving a dangling tool_result → structurally invalid.
        let retained = vec![tool_result("toolu_9")];
        assert!(!history_trim_is_valid(&retained));
    }

    #[test]
    fn plain_text_history_is_always_valid() {
        let retained = vec![
            json!({ "role": "user", "content": "hi" }),
            json!({ "role": "assistant", "content": "hello" }),
        ];
        assert!(history_trim_is_valid(&retained));
    }

    #[test]
    fn a_result_before_its_use_in_the_tail_is_still_valid() {
        // Order within the tail does not matter — both blocks are present.
        let retained = vec![tool_result("toolu_2"), tool_use("toolu_2")];
        assert!(history_trim_is_valid(&retained));
    }

    // --- L-0 validators (D-28) --------------------------------------------------

    fn blk(t: &str) -> Value {
        json!({ "type": "text", "text": t })
    }

    fn doc(system: Vec<Value>) -> Value {
        json!({
            "model": "claude-opus-4-8",
            "system": system,
            "messages": [ tool_use("toolu_1"), tool_result("toolu_1") ]
        })
    }

    #[test]
    fn a_genuine_permutation_validates() {
        let before = doc(vec![blk("a"), blk("b"), blk("c")]);
        let after = doc(vec![blk("b"), blk("c"), blk("a")]);
        assert!(reorder_is_structurally_valid(&before, &after));
    }

    #[test]
    fn a_dropped_block_does_not_validate() {
        let before = doc(vec![blk("a"), blk("b")]);
        let after = doc(vec![blk("b")]);
        assert!(!reorder_is_structurally_valid(&before, &after));
    }

    #[test]
    fn a_duplicated_block_does_not_validate() {
        let before = doc(vec![blk("a"), blk("b")]);
        let after = doc(vec![blk("a"), blk("a")]);
        assert!(!reorder_is_structurally_valid(&before, &after));
    }

    #[test]
    fn duplicate_blocks_are_matched_by_multiplicity_not_membership() {
        // Two identical blocks are a legitimate prompt; set equality would let a
        // transform silently drop one of them.
        let before = doc(vec![blk("a"), blk("a"), blk("b")]);
        assert!(reorder_is_structurally_valid(
            &before,
            &doc(vec![blk("b"), blk("a"), blk("a")])
        ));
        assert!(!reorder_is_structurally_valid(
            &before,
            &doc(vec![blk("a"), blk("b"), blk("b")])
        ));
    }

    #[test]
    fn an_edited_block_does_not_validate() {
        let before = doc(vec![blk("a"), blk("b")]);
        let after = doc(vec![blk("b"), blk("a ")]); // one trailing space
        assert!(!reorder_is_structurally_valid(&before, &after));
    }

    #[test]
    fn touching_messages_does_not_validate() {
        // The assertion that PROVES tool pairing and role alternation intact:
        // messages must be byte-identical, so nothing can orphan a pair.
        let before = doc(vec![blk("a")]);
        let mut after = before.clone();
        after["messages"] = json!([tool_result("toolu_1")]); // the tool_use dropped
        assert!(!reorder_is_structurally_valid(&before, &after));
        assert!(!insert_is_structurally_valid(&before, &after));
    }

    #[test]
    fn touching_any_other_top_level_key_does_not_validate() {
        let before = doc(vec![blk("a")]);
        let mut after = before.clone();
        after["model"] = json!("claude-haiku-4-5");
        assert!(!reorder_is_structurally_valid(&before, &after));

        let mut added = before.clone();
        added["temperature"] = json!(0.5);
        assert!(!reorder_is_structurally_valid(&before, &added));
    }

    #[test]
    fn adding_one_cache_control_marker_validates() {
        let before = doc(vec![blk("a"), blk("b")]);
        let mut after = before.clone();
        after["system"][1]["cache_control"] = json!({ "type": "ephemeral" });
        assert!(insert_is_structurally_valid(&before, &after));
    }

    #[test]
    fn insert_that_reorders_does_not_validate() {
        // This mechanism moves nothing; order must be preserved index-for-index.
        let before = doc(vec![blk("a"), blk("b")]);
        let after = doc(vec![blk("b"), blk("a")]);
        assert!(!insert_is_structurally_valid(&before, &after));
    }

    #[test]
    fn displacing_an_existing_marker_does_not_validate() {
        // Rewriting someone else's breakpoint would silently uncache whatever it
        // covered (D-19) — a removal inside a lever that removes nothing.
        let mut before = doc(vec![blk("a")]);
        before["system"][0]["cache_control"] = json!({ "type": "ephemeral", "ttl": "1h" });
        let mut after = before.clone();
        after["system"][0]["cache_control"] = json!({ "type": "ephemeral" });
        assert!(!insert_is_structurally_valid(&before, &after));
    }

    #[test]
    fn editing_text_while_adding_a_marker_does_not_validate() {
        let before = doc(vec![blk("a")]);
        let mut after = before.clone();
        after["system"][0]["text"] = json!("a!");
        after["system"][0]["cache_control"] = json!({ "type": "ephemeral" });
        assert!(!insert_is_structurally_valid(&before, &after));
    }

    #[test]
    fn a_string_valued_system_never_validates_for_either_mechanism() {
        let before = json!({ "system": "plain", "messages": [] });
        let after = json!({ "system": [ blk("plain") ], "messages": [] });
        assert!(!reorder_is_structurally_valid(&before, &after));
        assert!(!insert_is_structurally_valid(&before, &after));
    }
}