Config Patch Service: Safe Edits, Generated Diffs and Rebasing

Config Patch Service: Safe Edits, Generated Diffs and Rebasing

You've joined the platform team that owns cfgpatch, the service the rollout tooling uses to change production configuration. Configs are JSON documents. Teams change them by sending JSON Patch documents (a precise subset of RFC 6902, written out below). Last week three bad pushes corrupted live configs, and the roadmap has three features queued behind the fixes.

Documents and patches cross the API as JSON text (strings), and every document that comes back is the same canonical text: object keys sorted, no whitespace, non-ASCII characters written as themselves ({"a":1,"b":[1,2]}).

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh, empty service and returns exactly one result per operation. An operation is [name, *args]. Failures are returned, never raised, as "error: <code>" strings.

• Versions of a name count from 1. put and every successful apply commit a new version; the head is the newest. An apply with an empty patch [] still commits a new version.
• Argument checks come first and return "error: invalid arguments": the operation must be a non-empty list whose first item is a string; names must be non-empty strings; text and patch_text must be strings; versions must be integers that are not booleans; the wrong number of arguments. An unknown operation name returns "error: unknown operation" (checked before the argument count).
• Lookup errors then follow this order: unknown document, then unknown version, then invalid json (text that is not valid JSON, including NaN, Infinity), then the patch itself. get with a version outside 1..head is unknown version.
• A failure inside a patch is reported as "error: <code> at op <i>", where i is the 0-based position of the first operation that failed. "error: invalid patch" (the patch text is valid JSON but not a list) has no position.

JSON values. Documents never contain NaN, infinities, negative zero, or non-string keys. Equality is exact on type: two values are equal only when they have the same JSON type, and numbers must also have the same *kind*: 1 (integer) and 1.0 (float) are different values, and true is not 1. Objects ignore key order; arrays do not. 1.0 in JSON text parses as a float and is written back as 1.0. Everywhere this README says *equal*, it means this equality.

Worked example

[["put", "cfg", "{\"service\":\"gateway\",\"routes\":[\"a\",\"b\"],\"limits\":{\"rps\":100}}"],
 ["apply", "cfg", "[{\"op\":\"add\",\"path\":\"/routes/1\",\"value\":\"x\"},{\"op\":\"replace\",\"path\":\"/limits/rps\",\"value\":250},{\"op\":\"test\",\"path\":\"/routes/1\",\"value\":\"x\"}]"],
 ["get", "cfg"],
 ["get", "cfg", 1]]

returns

[1, 2,
 "{\"limits\":{\"rps\":250},\"routes\":[\"a\",\"x\",\"b\"],\"service\":\"gateway\"}",
 "{\"limits\":{\"rps\":100},\"routes\":[\"a\",\"b\"],\"service\":\"gateway\"}"]

Part 1: Stop corrupting configs (INC-4417)

Goal: make apply follow the patch rules below exactly. The incident review found these symptoms (there may be more than one cause behind each):

1. A push whose last operation failed left the config half applied, and the version history showed the damage in older versions too.
2. add /routes/1 replaced the second route instead of inserting before it.
3. Keys containing ~ and / could not be addressed reliably (a key literally named ~1 was unreachable).
4. A move of /a to /a/old deleted the section and nothing complained.
5. A test guard {"value": 1} passed against a config where the field was true.
6. Index tokens like -1 or 01 were accepted as array positions.

Rules

1. A patch is a JSON array of operation objects, applied in order, all-or-nothing. If any operation fails, nothing changes: no new version, and no stored version (new or old) is altered. A successful patch commits exactly one new version.
2. Shape. Each operation is an object with a string "op" that is one of add, remove, replace, move, copy, test, and a string "path". add, replace and test also need a "value" member (any JSON value, null included). move and copy also need a string "from". Anything else is invalid operation. Extra members are ignored. Shape is checked before pointers.
3. Pointers. A pointer is "" (the whole document) or a /-prefixed list of reference tokens separated by /. Inside a token ~1 means / and ~0 means ~. Decode ~1 first, then ~0 (so ~01 is the two characters ~1). A pointer that does not start with / (and is not empty), or in which ~ is followed by anything other than 0 or 1 (or by nothing), is invalid pointer. path is checked before from; both are checked before the document is looked at.
4. Array indices. A token addressing an array element must be one or more ASCII digits with no leading zero (0 itself is fine). Anything else, including -1, +1, 01, 1.0, spaces and non-ASCII digits, is invalid index. The token - is also invalid index, except as the final token of an add-style target (below), where it means "after the last element".
5. Walking a pointer goes token by token. In an object the key must exist, else path not found. In an array the token must be a valid index (else invalid index) and smaller than the length (else path not found). Walking into a number, string, boolean or null is path not found. The first failing token decides the error.
6. Operations

• add: with path "" the document becomes value. Otherwise the parent (all tokens but the last) must exist. In an object, the key is set (an existing key is overwritten). In an array, the last token - appends; otherwise it is an index i and value is inserted before the element currently at i, pushing later elements right. i equal to the length appends; i greater than the length is path not found. A scalar parent is path not found.
• remove: the target must exist (as in rule 5, last token included). Path "" is cannot remove root. Removing from an array shifts later elements left.
• replace: the target must exist; its value becomes value. Path "" replaces the document.
• move: in this order: (1) from must exist; (2) if from is a proper prefix of path (token by token: /a is a proper prefix of /a/b but not of /ab) the error is invalid move; (3) if from and path are the same pointer nothing happens; (4) the value is removed from from; (5) it is added at path with add rules, evaluated on the document after the removal.
• copy: from must exist; a deep copy of its value is added at path with add rules. Copies never share structure with the original.
• test: the target must exist (path not found) and be equal to value, else test failed.

1. No shared structure. Values written by add, replace and copy are independent copies: a later operation that edits one of them never changes the patch text's parsed value, another place in the document, or any stored version.

Where to look: error codes in errors.py; each rule above lives in pointer.py, navigate.py, operations.py, engine.py, service.py and jsonvalue.py. tests/ has two failing tests, but they do not cover everything above.

Part 2: Generate a patch from two documents (CFG-212)

Goal: implement diff(a, b): given the heads of two documents, return the patch that turns a into b. Reviewers diff configs a hundred times a day, so the output must be exactly reproducible: the same two documents always give the same patch, byte for byte. Applying the patch to a with Part 1's apply must produce b (the round trip).

diff returns canonical text of a JSON array. Operations are written as {"op": "remove", "path": P}, {"op": "add", "path": P, "value": V} or {"op": "replace", "path": P, "value": V} (and, from Part 3, {"op": "move", "from": P, "path": Q}). Pointers escape ~ as ~0 and / as ~1. diff_stats(a, b) returns {"ops": N, "add": n, "remove": n, "replace": n, "move": n, "digest": D, "roundtrip": bool}, where D is the first 12 hex characters of the SHA-1 of the patch's canonical text (UTF-8), and roundtrip says whether applying the patch to a gave text equal to b's. (service.diff_stats is already written and calls your code.)

Rules

1. diff_value(x, y) at some location:

• if x and y are equal, nothing;
• both objects: visit the keys of x ∪ y in sorted order (Python's default string ordering). A key only in x is removed; a key only in y is added (with its value); a key in both is diffed recursively;
• both arrays: align them (rule 2) and handle gaps (rule 3);
• otherwise (different types, or two different scalars): one replace at that location with y (path "" at the top).

1. Array alignment pairs up equal elements. Let A and B be the arrays. (a) Match the longest common prefix element by element. (b) Of what remains, match the longest common suffix (never overlapping the prefix). (c) For the middle parts A' and B', let L(i, j) be the length of the longest common subsequence of A'[i:] and B'[j:]. Walk from (0, 0): if A'[i] equals B'[j], match them and advance both; otherwise, if L(i+1, j) == L(i, j) delete A'[i]; otherwise insert B'[j]. When one side is used up, the rest of the other is deleted or inserted.
2. Gaps. Between consecutive matches (and before the first / after the last) the unmatched elements of A form a list D and the unmatched elements of B a list I; let t = min(|D|, |I|). The first t elements of D are paired with the first t of I in order, and each pair is diffed recursively (rule 1), so [{"a":1}] to [{"a":2}] gives replace /0/a. The other |D| - t elements are removed, the other |I| - t are added.
3. Two phases. Every remove comes before every add and replace: the patch is *all removals, in traversal order,* followed by *all adds and replaces, in traversal order.* Traversal order visits object keys in sorted order and arrays left to right (inside a gap: the recursion into pairs first, then the extra removals or extra adds).
4. Array positions. A removal's index is the number of elements to its left in A that are not removed (matched or paired elements, including those in earlier gaps). The |D| - t extra removals of one gap therefore all use the same index. An add's index, and the index used for a recursive change inside an added/paired element in phase 2, is the element's final position in B. Inside a pair, the phase-1 path uses the survivor count and the phase-2 path uses the position in B. An add at the end of an array uses the numeric index (never -).

Worked example

a = {"name":"edge","ttl":30,"tags":["a"],"old":true}, b = {"name":"edge","ttl":60,"tags":["a","b"],"region":"eu"}:

[{"op":"remove","path":"/old"},
 {"op":"add","path":"/region","value":"eu"},
 {"op":"add","path":"/tags/1","value":"b"},
 {"op":"replace","path":"/ttl","value":60}]

Rule 2(b) matters: ["p","x"] to ["x","x"] is [{"op":"replace","path":"/0","value":"x"}] (the last x is matched as a suffix first), and ["a"] to ["a","a"] is [{"op":"add","path":"/1","value":"a"}].

Part 3: Move detection and stale-base rebasing (CFG-240, CFG-251)

Two requests landed at once. They change what diff returns, so Part 2 outputs change when the conditions below hold; Part 2's other rules stay.

3a. Moves

Goal: when something is removed in one place and the same value is added somewhere else, diff should say so with one move instead of a remove plus an add.

After building the patch exactly as in Part 2, post-process the list of operations:

1. A remove is movable when the value it removes (the value that was at that path in a) is a non-empty object or non-empty array. Scalars, {} and [] are never moved.
2. A remove R may pair with a later add A (A after R in the list) when A's value is equal to R's removed value.
3. Blocked pairs. Look at the tokens of R's pointer that index into arrays of a and take the *outermost* such array (for R = /x/y/3/z where /x/y is an array in a, that is /x/y; for R = /l/0 it is /l; if R's pointer indexes into no array, R is never blocked). R is blocked from pairing with A if any operation strictly between them in the list has a path (or, for a move, a from) that lies inside that array (starts with its pointer and is longer). Moving across such an operation would change which element an index refers to.
4. Procedure. Repeat until nothing changes: find the first remove in the list that has any eligible add (rules 1-3) and pair it with the first eligible add after it. Replace that add with {"op":"move","from":<R's path>,"path":<A's path>} and delete R. A move created this way can sit between other pairs (rule 3 looks at its path and from) but is never paired again.

move has the Part 1 meaning (remove at from, then add at path evaluated after the removal), so the round trip still holds. The diff_stats move counter counts them.

Worked example. a = {"db":{"host":"h","port":5432},"app":{"name":"x"}}, b = {"app":{"name":"x"},"database":{"host":"h","port":5432}} gives [{"from":"/db","op":"move","path":"/database"}] (keys print in sorted order in canonical text). [X, Y, Z] to [Y, Z, X] (objects) gives one move from /0 to /2; if the same diff also had to insert a new element into that array between the remove and the add, the pair is blocked and you keep remove + add.

3b. Applying a patch written against an older version

Goal: a client fetched version v, prepared a patch, and by the time it is submitted the head has moved on. Support rebase and a stale-base apply.

• ["rebase", name, patch_text, base_version] returns the patch to run on the current head that carries the client's intent. It changes nothing in the store.
• ["apply", name, patch_text, base_version]: if base_version equals the head's version it is exactly Part 1's apply. Otherwise it applies the rebased patch (with Part 1's apply rules, all-or-nothing) and commits one new version.

Rules

1. Lookups in order: unknown document, unknown version (for base_version outside 1..head), invalid json. Then base is the stored document at base_version, head the current head.
2. Replay. Apply the patch to base with Part 1 rules. Any failure is reported with Part 1's <code> at op <i>; the head plays no part (a patch is checked against the document its author saw). The result is mine.
3. Merge. merge(base, mine, head) works value by value, with "missing" as a possible value: (i) if mine equals base, the result is head's value; (ii) else if head equals base, it is mine; (iii) else if mine equals head, that value; (iv) else if all three are objects, merge each key of the union in sorted order and drop keys whose merged result is "missing"; (v) otherwise conflict. Arrays are atomic: two different changes to an array (or one change to an array and a delete of it) always conflict.
4. A conflict fails with "error: conflict at <pointer>", naming the first conflicting location in that sorted traversal (the root, which cannot be a key, is written (root)). Nothing changes.
5. Otherwise the rebased patch is diff(head, merged) using the full diff of Parts 2 and 3a (so it contains moves, is normalized, and is empty when the head already has everything). rebase returns it even when base_version is the head's version.

Worked example

[["put", "cfg", "{\"a\":1,\"b\":{\"x\":1},\"l\":[1]}"],
 ["apply", "cfg", "[{\"op\":\"replace\",\"path\":\"/b/x\",\"value\":2}]"],
 ["rebase", "cfg", "[{\"op\":\"replace\",\"path\":\"/a\",\"value\":5},{\"op\":\"add\",\"path\":\"/c\",\"value\":{\"k\":1}}]", 1],
 ["apply", "cfg", "[{\"op\":\"replace\",\"path\":\"/a\",\"value\":5},{\"op\":\"add\",\"path\":\"/c\",\"value\":{\"k\":1}}]", 1],
 ["get", "cfg"],
 ["rebase", "cfg", "[{\"op\":\"replace\",\"path\":\"/b/x\",\"value\":3}]", 1]]

returns [1, 2, "<the same two operations, as canonical text>", 3, "{\"a\":5,\"b\":{\"x\":2},\"c\":{\"k\":1},\"l\":[1]}", "error: conflict at /b/x"].

Part 4: Big documents (CFG-266)

Goal: diff must stay fast on the long route tables the platform team ships, without changing a single byte of its output (Parts 2 and 3 rules are the spec; the digest in diff_stats makes any deviation visible).

Two operations, already implemented in fixtures.py, build big documents from a few arguments:

• ["gen", name, {"n": N, "seed": S}] stores a document {"service": "...", "routes": [N route objects]} as the next version of name (returns the version). Routes repeat a lot.
• ["mutate", source, target, {"seed": S, "edits": E}] stores, as the next version of target, a copy of the head of source with E pseudo-random edits to its routes (delete, insert, modify, or move one route). Returns the version.

Both argument dictionaries must have non-negative integer members; anything else is invalid arguments.

Hidden tests call diff_stats on documents with thousands of routes and a few dozen differences. Comparing every element against every element will not finish, and neither will comparing nested values with a recursive function inside a quadratic loop. Whatever you change must give the same alignment, the same patch and the same digest as the rules above (the tie-breaks in rule 2 are part of the spec, and so is the blocked-pair rule for moves).

Constraints

• Python 3 standard library only; no wall clock, randomness or iteration-order effects in results.
• Earlier Parts keep working after later ones (the hidden tests mix them).