Something went wrong. Try again.
Cooperative email for PDS operators
Something went wrong. Try again.
15 kB · 463 lines
Go
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464// Copyright (c) 2021 Tailscale Inc & AUTHORS All rights reserved.// Use of this source code is governed by a BSD-style// license that can be found in the LICENSE file.
package hujson
import ( "bytes" "encoding/json" "fmt" "reflect" "strings")
// TODO(dsnet): Insert/remove operations on an array has O(n) complexity// where n is the length of the array. We could improve this with more clever// data structure that has efficient insertion, deletion, and indexing.// One possibility is an "order statistic tree", which provide O(log n)// behavior for the necessary operations.// See https://en.wikipedia.org/wiki/Order_statistic_tree.
// TODO(dsnet): Name lookup on an object has O(n) complexity performing// a linear search through all names. This can be alleviated by building// a map of names to indexes for relevant objects. Currently, we always insert// a new member at the end of the members list, so that operation carries an// amortized cost of O(1).
// TODO(dsnet): Cache intermediate lookups when resolving a JSON pointer.// Patch operations tend to operate on paths that are related.// Caching can reduce pointer lookup from O(n) to be closer to O(1)// where n is the number of path segments in the JSON pointer.
// TODO(dsnet): Batch sequential insert/remove operations performed// on the same object or array. This handles the possibly common case of batch// inserting or removing a number of consecutive members/elements.// Pointer caching may make this optimization unnecessary.
// Patch patches the value according to the provided patch file (per RFC 6902).// The patch file may be in the HuJSON format where comments around and within// a value being inserted are preserved. If the patch fails to fully apply,// the receiver value will be left in a partially mutated state.// Use Clone to preserve the original value.//// It does not format the value. It is recommended that Format be called after// applying a patch.func (v *Value) Patch(patch []byte) error { ops, err := parsePatch(patch) if err != nil { return err } for i, op := range ops { var err error switch op.op { case "add": err = v.patchAdd(i, op) case "remove", "replace": err = v.patchRemoveOrReplace(i, op) case "move", "copy": err = v.patchMoveOrCopy(i, op) case "test": err = v.patchTest(i, op) } if err != nil { return err } } return nil}
type patchOperation struct { op string // "add" | "remove" | "replace" | "move" | "copy" | "test" path string // used by all operations from string // used by "move" and "copy" value Value // used by "add", "replace", and "test"}
func parsePatch(patch []byte) ([]patchOperation, error) { v, err := Parse(patch) if err != nil { return nil, err } arr, ok := v.Value.(*Array) if !ok { return nil, fmt.Errorf("hujson: patch must be a JSON array") } var ops []patchOperation for i, e := range arr.Elements { obj, ok := e.Value.(*Object) if !ok { return nil, fmt.Errorf("hujson: patch operation %d: must be a JSON object", i) } seen := make(map[string]bool) var op patchOperation for j, m := range obj.Members { name := m.Name.Value.(Literal).String() if seen[name] { return nil, fmt.Errorf("hujson: patch operation %d: duplicate name %q", i, m.Name.Value) } seen[name] = true switch name { case "op": if m.Value.Value.Kind() != '"' { return nil, fmt.Errorf("hujson: patch operation %d: member %q must be a JSON string", i, name) } switch opType := m.Value.Value.(Literal).String(); opType { case "add", "remove", "replace", "move", "copy", "test": op.op = opType default: return nil, fmt.Errorf("hujson: patch operation %d: unknown operation %q", i, m.Value.Value) } case "path": if m.Value.Value.Kind() != '"' { return nil, fmt.Errorf("hujson: patch operation %d: member %q must be a JSON string", i, name) } op.path = m.Value.Value.(Literal).String() case "from": if m.Value.Value.Kind() != '"' { return nil, fmt.Errorf("hujson: patch operation %d: member %q must be a JSON string", i, name) } op.from = m.Value.Value.(Literal).String() case "value": m.Value.BeforeExtra = obj.beforeExtraAt(j + 0).extractLeadingComments(true) m.Value.AfterExtra = obj.beforeExtraAt(j + 1).extractTrailingcomments(true) op.value = m.Value } } switch { case !seen["op"]: return nil, fmt.Errorf("hujson: patch operation %d: missing required member %q", i, "op") case !seen["path"]: return nil, fmt.Errorf("hujson: patch operation %d: missing required member %q", i, "path") case !seen["from"] && (op.op == "move" || op.op == "copy"): return nil, fmt.Errorf("hujson: patch operation %d: missing required member %q", i, "from") case !seen["value"] && (op.op == "add" || op.op == "replace" || op.op == "test"): return nil, fmt.Errorf("hujson: patch operation %d: missing required member %q", i, "value") } ops = append(ops, op) } return ops, nil}
func (v *Value) patchAdd(i int, op patchOperation) error { s, err := v.find(findState{pointer: op.path}) if err != nil && (err != errNotFound || len(s.pointer) != s.offset) { return fmt.Errorf("hujson: patch operation %d: %v", i, err) } if s.parent == nil { *v = op.value // only occurs for root } else { switch comp := s.parent.(type) { case *Object: if s.idx < comp.length() { replaceAt(comp, s.idx, op.value) } else { insertAt(comp, s.idx, op.value) comp.Members[s.idx].Name.Value = String(s.name) } case *Array: insertAt(comp, s.idx, op.value) } } return nil}
func (v *Value) patchRemoveOrReplace(i int, op patchOperation) error { s, err := v.find(findState{pointer: op.path}) if err != nil { return fmt.Errorf("hujson: patch operation %d: %v", i, err) } if s.parent == nil { return fmt.Errorf("hujson: patch operation %d: cannot %s root value", i, op.op) } switch op.op { case "remove": removeAt(s.parent, s.idx) case "replace": replaceAt(s.parent, s.idx, op.value) } return nil}
func (v *Value) patchMoveOrCopy(i int, op patchOperation) error { if op.from == "" || (op.op == "move" && hasPathPrefix(op.path, op.from)) { return fmt.Errorf("hujson: patch operation %d: cannot %s %q into %q", i, op.op, op.from, op.path) } sFrom, err := v.find(findState{pointer: op.from}) if err != nil { return fmt.Errorf("hujson: patch operation %d: %v", i, err) } // TODO(dsnet): For a move operation within the same object, // we should simplify this as just a rename or replace. switch op.op { case "move": op.value = removeAt(sFrom.parent, sFrom.idx) case "copy": op.value = copyAt(sFrom.parent, sFrom.idx) } return v.patchAdd(i, op)}
func (v *Value) patchTest(i int, op patchOperation) error { s, err := v.find(findState{pointer: op.path}) if err != nil { return fmt.Errorf("hujson: patch operation %d: %v", i, err) } if !equalValue(*s.value, op.value) { return fmt.Errorf("hujson: patch operation %d: values differ at %q", i, op.path)
} return nil}
// hasPathPrefix is a stricter version of strings.HasPrefix where// the prefix must end on a path segment boundary.func hasPathPrefix(s, prefix string) bool { if strings.HasPrefix(s, prefix) { return len(s) == len(prefix) || s[len(prefix)] == '/' } return false}
func equalValue(x, y Value) bool { // TODO(dsnet): This definition of equality is both naive and slow. // * It fails to properly compare strings with invalid UTF-8. // * It fails to precisely compare integers beyond ±2⁵³. // * It cannot handle values greater than ±math.MaxFloat64. // * Comparison of objects with duplicate names has undefined behavior. unmarshal := func(v Value) (vi interface{}) { v = v.Clone() v.Standardize() if json.Unmarshal(v.Pack(), &vi) != nil { return nil } return vi } vx := unmarshal(x) vy := unmarshal(y) return reflect.DeepEqual(vx, vy) && vx != nil && vy != nil}
func (obj *Object) getAt(i int) ValueTrimmed { return obj.Members[i].Value.Value}func (obj *Object) setAt(i int, v ValueTrimmed) { obj.Members[i].Value.Value = v}func (obj *Object) insertAt(i int, v ValueTrimmed) { // TODO(dsnet): Use slices.Insert. See https://golang.org/issue/45955. obj.Members = append(obj.Members, ObjectMember{}) copy(obj.Members[i+1:], obj.Members[i:]) obj.Members[i] = ObjectMember{Value: Value{Value: v}}}func (obj *Object) removeAt(i int) ValueTrimmed { // TODO(dsnet): Use slices.Delete. See https://golang.org/issue/45955. v := obj.Members[i].Value.Value copy(obj.Members[i:], obj.Members[i+1:]) obj.Members = obj.Members[:obj.length()-1] return v}
func (arr *Array) getAt(i int) ValueTrimmed { return arr.Elements[i].Value}func (arr *Array) setAt(i int, v ValueTrimmed) { arr.Elements[i].Value = v}func (arr *Array) insertAt(i int, v ValueTrimmed) { // TODO(dsnet): Use slices.Insert. See https://golang.org/issue/45955. arr.Elements = append(arr.Elements, ArrayElement{}) copy(arr.Elements[i+1:], arr.Elements[i:]) arr.Elements[i] = ArrayElement{Value: v}}func (arr *Array) removeAt(i int) ValueTrimmed { // TODO(dsnet): Use slices.Delete. See https://golang.org/issue/45955. v := arr.Elements[i].Value copy(arr.Elements[i:], arr.Elements[i+1:]) arr.Elements = arr.Elements[:arr.length()-1] return v}
// Preserving and moving comments is impossible to perform reasonably in all// conceivable situations given that the placement of comments is more// a matter of human taste than it is a matter of mathematical rigor.//// We assume that:// * comments do not appear between the object member name and the colon// (i.e., ObjectMember.Name.AfterExtra is nil),// * comments do not appear between the colon and the object member value// (i.e., ObjectMember.Value.BeforeExtra is nil), and// * comments do not appear between the value and the comma// (i.e., ObjectMember.Value.AfterExtra and ArrayElement.AfterExtra are nil).// Such comments will be lost when patching.//// We further assume that:// * comments before an object member name and before an array element value// are strongly associated with that member/element, and// * comments immediately after an object member value and after an// array element value are strongly associated with that member/element.// Such comments will be moved along with the member/element.//// Consider the following example:// {// ...// // Comment1//// // Comment2// "name": "value", // Comment3// // Comment4//// // Comment5// ...// }//// Moving "/name" will move only Comment2, Comment3, and Comment4.// All other comments will be left alone.//// The above approach may perform contrary to expectation in this example:// {// // Comment1// "name1": "value1",// "name2": "value2",// "name3": "value3",// }//// Moving "/name1" will move Comment1. It is unclear whether Comment1 is// strongly associated with just "name1" or the entire sequence of members// from "name1" to "name2".
func copyAt(comp composite, i int) (v Value) { v.BeforeExtra = comp.beforeExtraAt(i + 0).extractLeadingComments(true) v.AfterExtra = comp.beforeExtraAt(i + 1).extractTrailingcomments(true) v.Value = comp.getAt(i).clone() return v}func replaceAt(comp composite, i int, v Value) { comp.beforeExtraAt(i + 0).injectLeadingComments(v.BeforeExtra) comp.beforeExtraAt(i + 1).injectTrailingComments(v.AfterExtra) comp.setAt(i, v.Value)}func insertAt(comp composite, i int, v Value) { comp.insertAt(i, v.Value) trailing := comp.beforeExtraAt(i + 1).extractTrailingcomments(false) comp.beforeExtraAt(i + 0).injectTrailingComments(trailing) comp.beforeExtraAt(i + 0).injectLeadingComments(v.BeforeExtra) comp.beforeExtraAt(i + 1).injectTrailingComments(v.AfterExtra)}func removeAt(comp composite, i int) (v Value) { v.BeforeExtra = comp.beforeExtraAt(i + 0).extractLeadingComments(false) v.AfterExtra = comp.beforeExtraAt(i + 1).extractTrailingcomments(false) if trailing := *comp.beforeExtraAt(i + 0); trailing.hasComment() { leading := *comp.beforeExtraAt(i + 1) leading = leading[consumeWhitespace(leading):] *comp.beforeExtraAt(i + 1) = append(trailing, leading...) } v.Value = comp.removeAt(i) return v}
// injectLeadingComments injects leading comments into the bottom of b.func (b *Extra) injectLeadingComments(leading Extra) { if len(leading) > 0 { _, currStart := b.classifyComments() blankLen := consumeWhitespace((*b)[currStart:]) *b = (*b)[:currStart+blankLen] leading = leading[consumeWhitespace(leading):] if len(leading) > 0 { if i := bytes.LastIndexByte(*b, '\n'); i < 0 || (*b)[i:].hasComment() { *b = append(*b, newline...) } *b = append(*b, leading...) } }}
// extractLeadingComments extracts leading comments from the bottom of b.// If readonly, then the source is not mutated.func (b *Extra) extractLeadingComments(readonly bool) (leading Extra) { _, currStart := b.classifyComments() blankLen := consumeWhitespace((*b)[currStart:]) leading = copyBytes((*b)[currStart+blankLen:]) if !readonly { *b = (*b)[:currStart+blankLen] } return leading}
// injectTrailingComments injects trailing comments into the top of b.func (b *Extra) injectTrailingComments(trailing Extra) { if len(trailing) > 0 { prevEnd, _ := b.classifyComments() if bytes.HasSuffix((*b)[:prevEnd], newline) { prevEnd-- // preserve trailing newline } *b = (*b)[prevEnd:] if trailing.hasComment() { if bytes.HasSuffix(trailing, newline) && bytes.HasPrefix(*b, newline) { trailing = trailing[:len(trailing)-1] // drop trailing newline } *b = append(copyBytes(trailing), *b...) } }}
// extractTrailingcomments extracts trailing comments from the top of b.// If readonly, then the source is not mutated.func (b *Extra) extractTrailingcomments(readonly bool) (trailing Extra) { prevEnd, _ := b.classifyComments() trailing = copyBytes((*b)[:prevEnd]) if !readonly { if bytes.HasSuffix(trailing, newline) { prevEnd-- // preserve trailing newline } *b = (*b)[prevEnd:] } return trailing}
// classifyComments classifies comments as belonging to the previous element// or belonging to the current element such that:// - b[:prevEnd] belongs to the previous element, and// - b[currStart:] belongs to the current element.//// Invariant: prevEnd <= currStartfunc (b Extra) classifyComments() (prevEnd, currStart int) { // Scan for dividers between comment blocks. var firstDivider, lastDivider, numDividers int var n, prevNewline int for len(b) > n { nw := consumeWhitespace(b[n:]) if prevNewline+bytes.Count(b[n:][:nw], newline) >= 2 { if numDividers == 0 { firstDivider = n } lastDivider = n numDividers++ } n += nw
nc := consumeComment(b[n:]) if nc <= 0 { break } prevNewline = 0 if bytes.HasSuffix(b[n:][:nc], newline) { prevNewline = 1 // adjust newline accounting for next iteration } n += nc }
// Without dividers, a line comment starting on the first line belongs // to the previous element. if numDividers == 0 { nw := consumeWhitespace(b) nc := consumeComment(b[nw:]) if n = nw + nc; bytes.Count(b[:n], newline) == 1 && bytes.HasSuffix(b[:n], lineCommentEnd) { return n, n } return 0, 0 }
// Ownership is more clear when there is at least one divider. return firstDivider, lastDivider}