patch.go

Documentation: github.com/evanphx/json-patch/v5

     1  package jsonpatch
     2  
     3  import (
     4  	"bytes"
     5  	"fmt"
     6  	"strconv"
     7  	"strings"
     8  	"unicode"
     9  
    10  	"github.com/evanphx/json-patch/v5/internal/json"
    11  	"github.com/pkg/errors"
    12  )
    13  
    14  const (
    15  	eRaw = iota
    16  	eDoc
    17  	eAry
    18  )
    19  
    20  var (
    21  	// SupportNegativeIndices decides whether to support non-standard practice of
    22  	// allowing negative indices to mean indices starting at the end of an array.
    23  	// Default to true.
    24  	SupportNegativeIndices bool = true
    25  	// AccumulatedCopySizeLimit limits the total size increase in bytes caused by
    26  	// "copy" operations in a patch.
    27  	AccumulatedCopySizeLimit int64 = 0
    28  	startObject                    = json.Delim('{')
    29  	endObject                      = json.Delim('}')
    30  	startArray                     = json.Delim('[')
    31  	endArray                       = json.Delim(']')
    32  )
    33  
    34  var (
    35  	ErrTestFailed   = errors.New("test failed")
    36  	ErrMissing      = errors.New("missing value")
    37  	ErrUnknownType  = errors.New("unknown object type")
    38  	ErrInvalid      = errors.New("invalid state detected")
    39  	ErrInvalidIndex = errors.New("invalid index referenced")
    40  
    41  	ErrExpectedObject = errors.New("invalid value, expected object")
    42  
    43  	rawJSONArray  = []byte("[]")
    44  	rawJSONObject = []byte("{}")
    45  	rawJSONNull   = []byte("null")
    46  )
    47  
    48  type lazyNode struct {
    49  	raw   *json.RawMessage
    50  	doc   *partialDoc
    51  	ary   *partialArray
    52  	which int
    53  }
    54  
    55  // Operation is a single JSON-Patch step, such as a single 'add' operation.
    56  type Operation map[string]*json.RawMessage
    57  
    58  // Patch is an ordered collection of Operations.
    59  type Patch []Operation
    60  
    61  type partialDoc struct {
    62  	self *lazyNode
    63  	keys []string
    64  	obj  map[string]*lazyNode
    65  
    66  	opts *ApplyOptions
    67  }
    68  
    69  type partialArray struct {
    70  	self  *lazyNode
    71  	nodes []*lazyNode
    72  }
    73  
    74  type container interface {
    75  	get(key string, options *ApplyOptions) (*lazyNode, error)
    76  	set(key string, val *lazyNode, options *ApplyOptions) error
    77  	add(key string, val *lazyNode, options *ApplyOptions) error
    78  	remove(key string, options *ApplyOptions) error
    79  }
    80  
    81  // ApplyOptions specifies options for calls to ApplyWithOptions.
    82  // Use NewApplyOptions to obtain default values for ApplyOptions.
    83  type ApplyOptions struct {
    84  	// SupportNegativeIndices decides whether to support non-standard practice of
    85  	// allowing negative indices to mean indices starting at the end of an array.
    86  	// Default to true.
    87  	SupportNegativeIndices bool
    88  	// AccumulatedCopySizeLimit limits the total size increase in bytes caused by
    89  	// "copy" operations in a patch.
    90  	AccumulatedCopySizeLimit int64
    91  	// AllowMissingPathOnRemove indicates whether to fail "remove" operations when the target path is missing.
    92  	// Default to false.
    93  	AllowMissingPathOnRemove bool
    94  	// EnsurePathExistsOnAdd instructs json-patch to recursively create the missing parts of path on "add" operation.
    95  	// Default to false.
    96  	EnsurePathExistsOnAdd bool
    97  
    98  	EscapeHTML bool
    99  }
   100  
   101  // NewApplyOptions creates a default set of options for calls to ApplyWithOptions.
   102  func NewApplyOptions() *ApplyOptions {
   103  	return &ApplyOptions{
   104  		SupportNegativeIndices:   SupportNegativeIndices,
   105  		AccumulatedCopySizeLimit: AccumulatedCopySizeLimit,
   106  		AllowMissingPathOnRemove: false,
   107  		EnsurePathExistsOnAdd:    false,
   108  		EscapeHTML:               true,
   109  	}
   110  }
   111  
   112  func newLazyNode(raw *json.RawMessage) *lazyNode {
   113  	return &lazyNode{raw: raw, doc: nil, ary: nil, which: eRaw}
   114  }
   115  
   116  func newRawMessage(buf []byte) *json.RawMessage {
   117  	ra := make(json.RawMessage, len(buf))
   118  	copy(ra, buf)
   119  	return &ra
   120  }
   121  
   122  func (n *lazyNode) RedirectMarshalJSON() (any, error) {
   123  	switch n.which {
   124  	case eRaw:
   125  		return n.raw, nil
   126  	case eDoc:
   127  		return n.doc, nil
   128  	case eAry:
   129  		return n.ary.nodes, nil
   130  	default:
   131  		return nil, ErrUnknownType
   132  	}
   133  }
   134  
   135  func (n *lazyNode) UnmarshalJSON(data []byte) error {
   136  	dest := make(json.RawMessage, len(data))
   137  	copy(dest, data)
   138  	n.raw = &dest
   139  	n.which = eRaw
   140  	return nil
   141  }
   142  
   143  func (n *partialDoc) TrustMarshalJSON(buf *bytes.Buffer) error {
   144  	if n.obj == nil {
   145  		return ErrExpectedObject
   146  	}
   147  
   148  	if err := buf.WriteByte('{'); err != nil {
   149  		return err
   150  	}
   151  	escaped := true
   152  
   153  	// n.opts should always be set, but in case we missed a case,
   154  	// guard.
   155  	if n.opts != nil {
   156  		escaped = n.opts.EscapeHTML
   157  	}
   158  
   159  	for i, k := range n.keys {
   160  		if i > 0 {
   161  			if err := buf.WriteByte(','); err != nil {
   162  				return err
   163  			}
   164  		}
   165  		key, err := json.MarshalEscaped(k, escaped)
   166  		if err != nil {
   167  			return err
   168  		}
   169  		if _, err := buf.Write(key); err != nil {
   170  			return err
   171  		}
   172  		if err := buf.WriteByte(':'); err != nil {
   173  			return err
   174  		}
   175  		value, err := json.MarshalEscaped(n.obj[k], escaped)
   176  		if err != nil {
   177  			return err
   178  		}
   179  		if _, err := buf.Write(value); err != nil {
   180  			return err
   181  		}
   182  	}
   183  	if err := buf.WriteByte('}'); err != nil {
   184  		return err
   185  	}
   186  	return nil
   187  }
   188  
   189  type syntaxError struct {
   190  	msg string
   191  }
   192  
   193  func (err *syntaxError) Error() string {
   194  	return err.msg
   195  }
   196  
   197  func (n *partialDoc) UnmarshalJSON(data []byte) error {
   198  	keys, err := json.UnmarshalValidWithKeys(data, &n.obj)
   199  	if err != nil {
   200  		return err
   201  	}
   202  
   203  	n.keys = keys
   204  
   205  	return nil
   206  }
   207  
   208  func (n *partialArray) UnmarshalJSON(data []byte) error {
   209  	return json.UnmarshalValid(data, &n.nodes)
   210  }
   211  
   212  func (n *partialArray) RedirectMarshalJSON() (interface{}, error) {
   213  	return n.nodes, nil
   214  }
   215  
   216  func deepCopy(src *lazyNode, options *ApplyOptions) (*lazyNode, int, error) {
   217  	if src == nil {
   218  		return nil, 0, nil
   219  	}
   220  	a, err := json.MarshalEscaped(src, options.EscapeHTML)
   221  	if err != nil {
   222  		return nil, 0, err
   223  	}
   224  	sz := len(a)
   225  	return newLazyNode(newRawMessage(a)), sz, nil
   226  }
   227  
   228  func (n *lazyNode) nextByte() byte {
   229  	s := []byte(*n.raw)
   230  
   231  	for unicode.IsSpace(rune(s[0])) {
   232  		s = s[1:]
   233  	}
   234  
   235  	return s[0]
   236  }
   237  
   238  func (n *lazyNode) intoDoc(options *ApplyOptions) (*partialDoc, error) {
   239  	if n.which == eDoc {
   240  		return n.doc, nil
   241  	}
   242  
   243  	if n.raw == nil {
   244  		return nil, ErrInvalid
   245  	}
   246  
   247  	if n.nextByte() != '{' {
   248  		return nil, ErrInvalid
   249  	}
   250  
   251  	err := unmarshal(*n.raw, &n.doc)
   252  
   253  	if n.doc == nil {
   254  		return nil, ErrInvalid
   255  	}
   256  
   257  	n.doc.opts = options
   258  	if err != nil {
   259  		return nil, err
   260  	}
   261  
   262  	n.which = eDoc
   263  	return n.doc, nil
   264  }
   265  
   266  func (n *lazyNode) intoAry() (*partialArray, error) {
   267  	if n.which == eAry {
   268  		return n.ary, nil
   269  	}
   270  
   271  	if n.raw == nil {
   272  		return nil, ErrInvalid
   273  	}
   274  
   275  	err := unmarshal(*n.raw, &n.ary)
   276  
   277  	if err != nil {
   278  		return nil, err
   279  	}
   280  
   281  	n.which = eAry
   282  	return n.ary, nil
   283  }
   284  
   285  func (n *lazyNode) compact() []byte {
   286  	buf := &bytes.Buffer{}
   287  
   288  	if n.raw == nil {
   289  		return nil
   290  	}
   291  
   292  	err := json.Compact(buf, *n.raw)
   293  
   294  	if err != nil {
   295  		return *n.raw
   296  	}
   297  
   298  	return buf.Bytes()
   299  }
   300  
   301  func (n *lazyNode) tryDoc() bool {
   302  	if n.raw == nil {
   303  		return false
   304  	}
   305  
   306  	err := unmarshal(*n.raw, &n.doc)
   307  
   308  	if err != nil {
   309  		return false
   310  	}
   311  
   312  	if n.doc == nil {
   313  		return false
   314  	}
   315  
   316  	n.which = eDoc
   317  	return true
   318  }
   319  
   320  func (n *lazyNode) tryAry() bool {
   321  	if n.raw == nil {
   322  		return false
   323  	}
   324  
   325  	err := unmarshal(*n.raw, &n.ary)
   326  
   327  	if err != nil {
   328  		return false
   329  	}
   330  
   331  	n.which = eAry
   332  	return true
   333  }
   334  
   335  func (n *lazyNode) isNull() bool {
   336  	if n == nil {
   337  		return true
   338  	}
   339  
   340  	if n.raw == nil {
   341  		return true
   342  	}
   343  
   344  	return bytes.Equal(n.compact(), rawJSONNull)
   345  }
   346  
   347  func (n *lazyNode) equal(o *lazyNode) bool {
   348  	if n.which == eRaw {
   349  		if !n.tryDoc() && !n.tryAry() {
   350  			if o.which != eRaw {
   351  				return false
   352  			}
   353  
   354  			nc := n.compact()
   355  			oc := o.compact()
   356  
   357  			if nc[0] == '"' && oc[0] == '"' {
   358  				// ok, 2 strings
   359  
   360  				var ns, os string
   361  
   362  				err := json.UnmarshalValid(nc, &ns)
   363  				if err != nil {
   364  					return false
   365  				}
   366  				err = json.UnmarshalValid(oc, &os)
   367  				if err != nil {
   368  					return false
   369  				}
   370  
   371  				return ns == os
   372  			}
   373  
   374  			return bytes.Equal(nc, oc)
   375  		}
   376  	}
   377  
   378  	if n.which == eDoc {
   379  		if o.which == eRaw {
   380  			if !o.tryDoc() {
   381  				return false
   382  			}
   383  		}
   384  
   385  		if o.which != eDoc {
   386  			return false
   387  		}
   388  
   389  		if len(n.doc.obj) != len(o.doc.obj) {
   390  			return false
   391  		}
   392  
   393  		for k, v := range n.doc.obj {
   394  			ov, ok := o.doc.obj[k]
   395  
   396  			if !ok {
   397  				return false
   398  			}
   399  
   400  			if (v == nil) != (ov == nil) {
   401  				return false
   402  			}
   403  
   404  			if v == nil && ov == nil {
   405  				continue
   406  			}
   407  
   408  			if !v.equal(ov) {
   409  				return false
   410  			}
   411  		}
   412  
   413  		return true
   414  	}
   415  
   416  	if o.which != eAry && !o.tryAry() {
   417  		return false
   418  	}
   419  
   420  	if len(n.ary.nodes) != len(o.ary.nodes) {
   421  		return false
   422  	}
   423  
   424  	for idx, val := range n.ary.nodes {
   425  		if !val.equal(o.ary.nodes[idx]) {
   426  			return false
   427  		}
   428  	}
   429  
   430  	return true
   431  }
   432  
   433  // Kind reads the "op" field of the Operation.
   434  func (o Operation) Kind() string {
   435  	if obj, ok := o["op"]; ok && obj != nil {
   436  		var op string
   437  
   438  		err := unmarshal(*obj, &op)
   439  
   440  		if err != nil {
   441  			return "unknown"
   442  		}
   443  
   444  		return op
   445  	}
   446  
   447  	return "unknown"
   448  }
   449  
   450  // Path reads the "path" field of the Operation.
   451  func (o Operation) Path() (string, error) {
   452  	if obj, ok := o["path"]; ok && obj != nil {
   453  		var op string
   454  
   455  		err := unmarshal(*obj, &op)
   456  
   457  		if err != nil {
   458  			return "unknown", err
   459  		}
   460  
   461  		return op, nil
   462  	}
   463  
   464  	return "unknown", errors.Wrapf(ErrMissing, "operation missing path field")
   465  }
   466  
   467  // From reads the "from" field of the Operation.
   468  func (o Operation) From() (string, error) {
   469  	if obj, ok := o["from"]; ok && obj != nil {
   470  		var op string
   471  
   472  		err := unmarshal(*obj, &op)
   473  
   474  		if err != nil {
   475  			return "unknown", err
   476  		}
   477  
   478  		return op, nil
   479  	}
   480  
   481  	return "unknown", errors.Wrapf(ErrMissing, "operation, missing from field")
   482  }
   483  
   484  func (o Operation) value() *lazyNode {
   485  	if obj, ok := o["value"]; ok {
   486  		// A `null` gets decoded as a nil RawMessage, so let's fix it up here.
   487  		if obj == nil {
   488  			return newLazyNode(newRawMessage(rawJSONNull))
   489  		}
   490  		return newLazyNode(obj)
   491  	}
   492  
   493  	return nil
   494  }
   495  
   496  // ValueInterface decodes the operation value into an interface.
   497  func (o Operation) ValueInterface() (interface{}, error) {
   498  	if obj, ok := o["value"]; ok {
   499  		if obj == nil {
   500  			return nil, nil
   501  		}
   502  
   503  		var v interface{}
   504  
   505  		err := unmarshal(*obj, &v)
   506  
   507  		if err != nil {
   508  			return nil, err
   509  		}
   510  
   511  		return v, nil
   512  	}
   513  
   514  	return nil, errors.Wrapf(ErrMissing, "operation, missing value field")
   515  }
   516  
   517  func isArray(buf []byte) bool {
   518  Loop:
   519  	for _, c := range buf {
   520  		switch c {
   521  		case ' ':
   522  		case '\n':
   523  		case '\t':
   524  			continue
   525  		case '[':
   526  			return true
   527  		default:
   528  			break Loop
   529  		}
   530  	}
   531  
   532  	return false
   533  }
   534  
   535  func findObject(pd *container, path string, options *ApplyOptions) (container, string) {
   536  	doc := *pd
   537  
   538  	split := strings.Split(path, "/")
   539  
   540  	if len(split) < 2 {
   541  		if path == "" {
   542  			return doc, ""
   543  		}
   544  		return nil, ""
   545  	}
   546  
   547  	parts := split[1 : len(split)-1]
   548  
   549  	key := split[len(split)-1]
   550  
   551  	var err error
   552  
   553  	for _, part := range parts {
   554  
   555  		next, ok := doc.get(decodePatchKey(part), options)
   556  
   557  		if next == nil || ok != nil {
   558  			return nil, ""
   559  		}
   560  
   561  		if isArray(*next.raw) {
   562  			doc, err = next.intoAry()
   563  
   564  			if err != nil {
   565  				return nil, ""
   566  			}
   567  		} else {
   568  			doc, err = next.intoDoc(options)
   569  
   570  			if err != nil {
   571  				return nil, ""
   572  			}
   573  		}
   574  	}
   575  
   576  	return doc, decodePatchKey(key)
   577  }
   578  
   579  func (d *partialDoc) set(key string, val *lazyNode, options *ApplyOptions) error {
   580  	if d.obj == nil {
   581  		return ErrExpectedObject
   582  	}
   583  
   584  	found := false
   585  	for _, k := range d.keys {
   586  		if k == key {
   587  			found = true
   588  			break
   589  		}
   590  	}
   591  	if !found {
   592  		d.keys = append(d.keys, key)
   593  	}
   594  	d.obj[key] = val
   595  	return nil
   596  }
   597  
   598  func (d *partialDoc) add(key string, val *lazyNode, options *ApplyOptions) error {
   599  	return d.set(key, val, options)
   600  }
   601  
   602  func (d *partialDoc) get(key string, options *ApplyOptions) (*lazyNode, error) {
   603  	if key == "" {
   604  		return d.self, nil
   605  	}
   606  
   607  	if d.obj == nil {
   608  		return nil, ErrExpectedObject
   609  	}
   610  
   611  	v, ok := d.obj[key]
   612  	if !ok {
   613  		return v, errors.Wrapf(ErrMissing, "unable to get nonexistent key: %s", key)
   614  	}
   615  	return v, nil
   616  }
   617  
   618  func (d *partialDoc) remove(key string, options *ApplyOptions) error {
   619  	if d.obj == nil {
   620  		return ErrExpectedObject
   621  	}
   622  
   623  	_, ok := d.obj[key]
   624  	if !ok {
   625  		if options.AllowMissingPathOnRemove {
   626  			return nil
   627  		}
   628  		return errors.Wrapf(ErrMissing, "unable to remove nonexistent key: %s", key)
   629  	}
   630  	idx := -1
   631  	for i, k := range d.keys {
   632  		if k == key {
   633  			idx = i
   634  			break
   635  		}
   636  	}
   637  	d.keys = append(d.keys[0:idx], d.keys[idx+1:]...)
   638  	delete(d.obj, key)
   639  	return nil
   640  }
   641  
   642  // set should only be used to implement the "replace" operation, so "key" must
   643  // be an already existing index in "d".
   644  func (d *partialArray) set(key string, val *lazyNode, options *ApplyOptions) error {
   645  	idx, err := strconv.Atoi(key)
   646  	if err != nil {
   647  		return err
   648  	}
   649  
   650  	if idx < 0 {
   651  		if !options.SupportNegativeIndices {
   652  			return errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   653  		}
   654  		if idx < -len(d.nodes) {
   655  			return errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   656  		}
   657  		idx += len(d.nodes)
   658  	}
   659  
   660  	d.nodes[idx] = val
   661  	return nil
   662  }
   663  
   664  func (d *partialArray) add(key string, val *lazyNode, options *ApplyOptions) error {
   665  	if key == "-" {
   666  		d.nodes = append(d.nodes, val)
   667  		return nil
   668  	}
   669  
   670  	idx, err := strconv.Atoi(key)
   671  	if err != nil {
   672  		return errors.Wrapf(err, "value was not a proper array index: '%s'", key)
   673  	}
   674  
   675  	sz := len(d.nodes) + 1
   676  
   677  	ary := make([]*lazyNode, sz)
   678  
   679  	cur := d
   680  
   681  	if idx >= len(ary) {
   682  		return errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   683  	}
   684  
   685  	if idx < 0 {
   686  		if !options.SupportNegativeIndices {
   687  			return errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   688  		}
   689  		if idx < -len(ary) {
   690  			return errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   691  		}
   692  		idx += len(ary)
   693  	}
   694  
   695  	copy(ary[0:idx], cur.nodes[0:idx])
   696  	ary[idx] = val
   697  	copy(ary[idx+1:], cur.nodes[idx:])
   698  
   699  	d.nodes = ary
   700  	return nil
   701  }
   702  
   703  func (d *partialArray) get(key string, options *ApplyOptions) (*lazyNode, error) {
   704  	if key == "" {
   705  		return d.self, nil
   706  	}
   707  
   708  	idx, err := strconv.Atoi(key)
   709  
   710  	if err != nil {
   711  		return nil, err
   712  	}
   713  
   714  	if idx < 0 {
   715  		if !options.SupportNegativeIndices {
   716  			return nil, errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   717  		}
   718  		if idx < -len(d.nodes) {
   719  			return nil, errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   720  		}
   721  		idx += len(d.nodes)
   722  	}
   723  
   724  	if idx >= len(d.nodes) {
   725  		return nil, errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   726  	}
   727  
   728  	return d.nodes[idx], nil
   729  }
   730  
   731  func (d *partialArray) remove(key string, options *ApplyOptions) error {
   732  	idx, err := strconv.Atoi(key)
   733  	if err != nil {
   734  		return err
   735  	}
   736  
   737  	cur := d
   738  
   739  	if idx >= len(cur.nodes) {
   740  		if options.AllowMissingPathOnRemove {
   741  			return nil
   742  		}
   743  		return errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   744  	}
   745  
   746  	if idx < 0 {
   747  		if !options.SupportNegativeIndices {
   748  			return errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   749  		}
   750  		if idx < -len(cur.nodes) {
   751  			if options.AllowMissingPathOnRemove {
   752  				return nil
   753  			}
   754  			return errors.Wrapf(ErrInvalidIndex, "Unable to access invalid index: %d", idx)
   755  		}
   756  		idx += len(cur.nodes)
   757  	}
   758  
   759  	ary := make([]*lazyNode, len(cur.nodes)-1)
   760  
   761  	copy(ary[0:idx], cur.nodes[0:idx])
   762  	copy(ary[idx:], cur.nodes[idx+1:])
   763  
   764  	d.nodes = ary
   765  	return nil
   766  }
   767  
   768  func (p Patch) add(doc *container, op Operation, options *ApplyOptions) error {
   769  	path, err := op.Path()
   770  	if err != nil {
   771  		return errors.Wrapf(ErrMissing, "add operation failed to decode path")
   772  	}
   773  
   774  	// special case, adding to empty means replacing the container with the value given
   775  	if path == "" {
   776  		val := op.value()
   777  
   778  		var pd container
   779  		if (*val.raw)[0] == '[' {
   780  			pd = &partialArray{
   781  				self: val,
   782  			}
   783  		} else {
   784  			pd = &partialDoc{
   785  				self: val,
   786  				opts: options,
   787  			}
   788  		}
   789  
   790  		err := json.UnmarshalValid(*val.raw, pd)
   791  
   792  		if err != nil {
   793  			return err
   794  		}
   795  
   796  		*doc = pd
   797  
   798  		return nil
   799  	}
   800  
   801  	if options.EnsurePathExistsOnAdd {
   802  		err = ensurePathExists(doc, path, options)
   803  
   804  		if err != nil {
   805  			return err
   806  		}
   807  	}
   808  
   809  	con, key := findObject(doc, path, options)
   810  
   811  	if con == nil {
   812  		return errors.Wrapf(ErrMissing, "add operation does not apply: doc is missing path: \"%s\"", path)
   813  	}
   814  
   815  	err = con.add(key, op.value(), options)
   816  	if err != nil {
   817  		return errors.Wrapf(err, "error in add for path: '%s'", path)
   818  	}
   819  
   820  	return nil
   821  }
   822  
   823  // Given a document and a path to a key, walk the path and create all missing elements
   824  // creating objects and arrays as needed.
   825  func ensurePathExists(pd *container, path string, options *ApplyOptions) error {
   826  	doc := *pd
   827  
   828  	var err error
   829  	var arrIndex int
   830  
   831  	split := strings.Split(path, "/")
   832  
   833  	if len(split) < 2 {
   834  		return nil
   835  	}
   836  
   837  	parts := split[1:]
   838  
   839  	for pi, part := range parts {
   840  
   841  		// Have we reached the key part of the path?
   842  		// If yes, we're done.
   843  		if pi == len(parts)-1 {
   844  			return nil
   845  		}
   846  
   847  		target, ok := doc.get(decodePatchKey(part), options)
   848  
   849  		if target == nil || ok != nil {
   850  
   851  			// If the current container is an array which has fewer elements than our target index,
   852  			// pad the current container with nulls.
   853  			if arrIndex, err = strconv.Atoi(part); err == nil {
   854  				pa, ok := doc.(*partialArray)
   855  
   856  				if ok && arrIndex >= len(pa.nodes)+1 {
   857  					// Pad the array with null values up to the required index.
   858  					for i := len(pa.nodes); i <= arrIndex-1; i++ {
   859  						doc.add(strconv.Itoa(i), newLazyNode(newRawMessage(rawJSONNull)), options)
   860  					}
   861  				}
   862  			}
   863  
   864  			// Check if the next part is a numeric index or "-".
   865  			// If yes, then create an array, otherwise, create an object.
   866  			if arrIndex, err = strconv.Atoi(parts[pi+1]); err == nil || parts[pi+1] == "-" {
   867  				if arrIndex < 0 {
   868  
   869  					if !options.SupportNegativeIndices {
   870  						return errors.Wrapf(ErrInvalidIndex, "Unable to ensure path for invalid index: %d", arrIndex)
   871  					}
   872  
   873  					if arrIndex < -1 {
   874  						return errors.Wrapf(ErrInvalidIndex, "Unable to ensure path for negative index other than -1: %d", arrIndex)
   875  					}
   876  
   877  					arrIndex = 0
   878  				}
   879  
   880  				newNode := newLazyNode(newRawMessage(rawJSONArray))
   881  				doc.add(part, newNode, options)
   882  				doc, _ = newNode.intoAry()
   883  
   884  				// Pad the new array with null values up to the required index.
   885  				for i := 0; i < arrIndex; i++ {
   886  					doc.add(strconv.Itoa(i), newLazyNode(newRawMessage(rawJSONNull)), options)
   887  				}
   888  			} else {
   889  				newNode := newLazyNode(newRawMessage(rawJSONObject))
   890  
   891  				doc.add(part, newNode, options)
   892  				doc, err = newNode.intoDoc(options)
   893  				if err != nil {
   894  					return err
   895  				}
   896  			}
   897  		} else {
   898  			if isArray(*target.raw) {
   899  				doc, err = target.intoAry()
   900  
   901  				if err != nil {
   902  					return err
   903  				}
   904  			} else {
   905  				doc, err = target.intoDoc(options)
   906  
   907  				if err != nil {
   908  					return err
   909  				}
   910  			}
   911  		}
   912  	}
   913  
   914  	return nil
   915  }
   916  
   917  func validateOperation(op Operation) error {
   918  	switch op.Kind() {
   919  	case "add", "replace":
   920  		if _, err := op.ValueInterface(); err != nil {
   921  			return errors.Wrapf(err, "failed to decode 'value'")
   922  		}
   923  	case "move", "copy":
   924  		if _, err := op.From(); err != nil {
   925  			return errors.Wrapf(err, "failed to decode 'from'")
   926  		}
   927  	case "remove", "test":
   928  	default:
   929  		return fmt.Errorf("unsupported operation")
   930  	}
   931  
   932  	if _, err := op.Path(); err != nil {
   933  		return errors.Wrapf(err, "failed to decode 'path'")
   934  	}
   935  
   936  	return nil
   937  }
   938  
   939  func validatePatch(p Patch) error {
   940  	for _, op := range p {
   941  		if err := validateOperation(op); err != nil {
   942  			opData, infoErr := json.Marshal(op)
   943  			if infoErr != nil {
   944  				return errors.Wrapf(err, "invalid operation")
   945  			}
   946  
   947  			return errors.Wrapf(err, "invalid operation %s", opData)
   948  		}
   949  	}
   950  
   951  	return nil
   952  }
   953  
   954  func (p Patch) remove(doc *container, op Operation, options *ApplyOptions) error {
   955  	path, err := op.Path()
   956  	if err != nil {
   957  		return errors.Wrapf(ErrMissing, "remove operation failed to decode path")
   958  	}
   959  
   960  	con, key := findObject(doc, path, options)
   961  
   962  	if con == nil {
   963  		if options.AllowMissingPathOnRemove {
   964  			return nil
   965  		}
   966  		return errors.Wrapf(ErrMissing, "remove operation does not apply: doc is missing path: \"%s\"", path)
   967  	}
   968  
   969  	err = con.remove(key, options)
   970  	if err != nil {
   971  		return errors.Wrapf(err, "error in remove for path: '%s'", path)
   972  	}
   973  
   974  	return nil
   975  }
   976  
   977  func (p Patch) replace(doc *container, op Operation, options *ApplyOptions) error {
   978  	path, err := op.Path()
   979  	if err != nil {
   980  		return errors.Wrapf(err, "replace operation failed to decode path")
   981  	}
   982  
   983  	if path == "" {
   984  		val := op.value()
   985  
   986  		if val.which == eRaw {
   987  			if !val.tryDoc() {
   988  				if !val.tryAry() {
   989  					return errors.Wrapf(err, "replace operation value must be object or array")
   990  				}
   991  			} else {
   992  				val.doc.opts = options
   993  			}
   994  		}
   995  
   996  		switch val.which {
   997  		case eAry:
   998  			*doc = val.ary
   999  		case eDoc:
  1000  			*doc = val.doc
  1001  		case eRaw:
  1002  			return errors.Wrapf(err, "replace operation hit impossible case")
  1003  		}
  1004  
  1005  		return nil
  1006  	}
  1007  
  1008  	con, key := findObject(doc, path, options)
  1009  
  1010  	if con == nil {
  1011  		return errors.Wrapf(ErrMissing, "replace operation does not apply: doc is missing path: %s", path)
  1012  	}
  1013  
  1014  	_, ok := con.get(key, options)
  1015  	if ok != nil {
  1016  		return errors.Wrapf(ErrMissing, "replace operation does not apply: doc is missing key: %s", path)
  1017  	}
  1018  
  1019  	err = con.set(key, op.value(), options)
  1020  	if err != nil {
  1021  		return errors.Wrapf(err, "error in remove for path: '%s'", path)
  1022  	}
  1023  
  1024  	return nil
  1025  }
  1026  
  1027  func (p Patch) move(doc *container, op Operation, options *ApplyOptions) error {
  1028  	from, err := op.From()
  1029  	if err != nil {
  1030  		return errors.Wrapf(err, "move operation failed to decode from")
  1031  	}
  1032  
  1033  	if from == "" {
  1034  		return errors.Wrapf(ErrInvalid, "unable to move entire document to another path")
  1035  	}
  1036  
  1037  	con, key := findObject(doc, from, options)
  1038  
  1039  	if con == nil {
  1040  		return errors.Wrapf(ErrMissing, "move operation does not apply: doc is missing from path: %s", from)
  1041  	}
  1042  
  1043  	val, err := con.get(key, options)
  1044  	if err != nil {
  1045  		return errors.Wrapf(err, "error in move for path: '%s'", key)
  1046  	}
  1047  
  1048  	err = con.remove(key, options)
  1049  	if err != nil {
  1050  		return errors.Wrapf(err, "error in move for path: '%s'", key)
  1051  	}
  1052  
  1053  	path, err := op.Path()
  1054  	if err != nil {
  1055  		return errors.Wrapf(err, "move operation failed to decode path")
  1056  	}
  1057  
  1058  	con, key = findObject(doc, path, options)
  1059  
  1060  	if con == nil {
  1061  		return errors.Wrapf(ErrMissing, "move operation does not apply: doc is missing destination path: %s", path)
  1062  	}
  1063  
  1064  	err = con.add(key, val, options)
  1065  	if err != nil {
  1066  		return errors.Wrapf(err, "error in move for path: '%s'", path)
  1067  	}
  1068  
  1069  	return nil
  1070  }
  1071  
  1072  func (p Patch) test(doc *container, op Operation, options *ApplyOptions) error {
  1073  	path, err := op.Path()
  1074  	if err != nil {
  1075  		return errors.Wrapf(err, "test operation failed to decode path")
  1076  	}
  1077  
  1078  	if path == "" {
  1079  		var self lazyNode
  1080  
  1081  		switch sv := (*doc).(type) {
  1082  		case *partialDoc:
  1083  			self.doc = sv
  1084  			self.which = eDoc
  1085  		case *partialArray:
  1086  			self.ary = sv
  1087  			self.which = eAry
  1088  		}
  1089  
  1090  		if self.equal(op.value()) {
  1091  			return nil
  1092  		}
  1093  
  1094  		return errors.Wrapf(ErrTestFailed, "testing value %s failed", path)
  1095  	}
  1096  
  1097  	con, key := findObject(doc, path, options)
  1098  
  1099  	if con == nil {
  1100  		return errors.Wrapf(ErrMissing, "test operation does not apply: is missing path: %s", path)
  1101  	}
  1102  
  1103  	val, err := con.get(key, options)
  1104  	if err != nil && errors.Cause(err) != ErrMissing {
  1105  		return errors.Wrapf(err, "error in test for path: '%s'", path)
  1106  	}
  1107  
  1108  	ov := op.value()
  1109  
  1110  	if val == nil {
  1111  		if ov.isNull() {
  1112  			return nil
  1113  		}
  1114  		return errors.Wrapf(ErrTestFailed, "testing value %s failed", path)
  1115  	} else if ov.isNull() {
  1116  		return errors.Wrapf(ErrTestFailed, "testing value %s failed", path)
  1117  	}
  1118  
  1119  	if val.equal(op.value()) {
  1120  		return nil
  1121  	}
  1122  
  1123  	return errors.Wrapf(ErrTestFailed, "testing value %s failed", path)
  1124  }
  1125  
  1126  func (p Patch) copy(doc *container, op Operation, accumulatedCopySize *int64, options *ApplyOptions) error {
  1127  	from, err := op.From()
  1128  	if err != nil {
  1129  		return errors.Wrapf(err, "copy operation failed to decode from")
  1130  	}
  1131  
  1132  	con, key := findObject(doc, from, options)
  1133  
  1134  	if con == nil {
  1135  		return errors.Wrapf(ErrMissing, "copy operation does not apply: doc is missing from path: \"%s\"", from)
  1136  	}
  1137  
  1138  	val, err := con.get(key, options)
  1139  	if err != nil {
  1140  		return errors.Wrapf(err, "error in copy for from: '%s'", from)
  1141  	}
  1142  
  1143  	path, err := op.Path()
  1144  	if err != nil {
  1145  		return errors.Wrapf(ErrMissing, "copy operation failed to decode path")
  1146  	}
  1147  
  1148  	con, key = findObject(doc, path, options)
  1149  
  1150  	if con == nil {
  1151  		return errors.Wrapf(ErrMissing, "copy operation does not apply: doc is missing destination path: %s", path)
  1152  	}
  1153  
  1154  	valCopy, sz, err := deepCopy(val, options)
  1155  	if err != nil {
  1156  		return errors.Wrapf(err, "error while performing deep copy")
  1157  	}
  1158  
  1159  	(*accumulatedCopySize) += int64(sz)
  1160  	if options.AccumulatedCopySizeLimit > 0 && *accumulatedCopySize > options.AccumulatedCopySizeLimit {
  1161  		return NewAccumulatedCopySizeError(options.AccumulatedCopySizeLimit, *accumulatedCopySize)
  1162  	}
  1163  
  1164  	err = con.add(key, valCopy, options)
  1165  	if err != nil {
  1166  		return errors.Wrapf(err, "error while adding value during copy")
  1167  	}
  1168  
  1169  	return nil
  1170  }
  1171  
  1172  // Equal indicates if 2 JSON documents have the same structural equality.
  1173  func Equal(a, b []byte) bool {
  1174  	la := newLazyNode(newRawMessage(a))
  1175  	lb := newLazyNode(newRawMessage(b))
  1176  
  1177  	return la.equal(lb)
  1178  }
  1179  
  1180  // DecodePatch decodes the passed JSON document as an RFC 6902 patch.
  1181  func DecodePatch(buf []byte) (Patch, error) {
  1182  	if !json.Valid(buf) {
  1183  		return nil, ErrInvalid
  1184  	}
  1185  
  1186  	var p Patch
  1187  
  1188  	err := unmarshal(buf, &p)
  1189  
  1190  	if err != nil {
  1191  		return nil, err
  1192  	}
  1193  
  1194  	if err := validatePatch(p); err != nil {
  1195  		return nil, err
  1196  	}
  1197  
  1198  	return p, nil
  1199  }
  1200  
  1201  // Apply mutates a JSON document according to the patch, and returns the new
  1202  // document.
  1203  func (p Patch) Apply(doc []byte) ([]byte, error) {
  1204  	return p.ApplyWithOptions(doc, NewApplyOptions())
  1205  }
  1206  
  1207  // ApplyWithOptions mutates a JSON document according to the patch and the passed in ApplyOptions.
  1208  // It returns the new document.
  1209  func (p Patch) ApplyWithOptions(doc []byte, options *ApplyOptions) ([]byte, error) {
  1210  	return p.ApplyIndentWithOptions(doc, "", options)
  1211  }
  1212  
  1213  // ApplyIndent mutates a JSON document according to the patch, and returns the new
  1214  // document indented.
  1215  func (p Patch) ApplyIndent(doc []byte, indent string) ([]byte, error) {
  1216  	return p.ApplyIndentWithOptions(doc, indent, NewApplyOptions())
  1217  }
  1218  
  1219  // ApplyIndentWithOptions mutates a JSON document according to the patch and the passed in ApplyOptions.
  1220  // It returns the new document indented.
  1221  func (p Patch) ApplyIndentWithOptions(doc []byte, indent string, options *ApplyOptions) ([]byte, error) {
  1222  	if len(doc) == 0 {
  1223  		return doc, nil
  1224  	}
  1225  
  1226  	if !json.Valid(doc) {
  1227  		return nil, ErrInvalid
  1228  	}
  1229  
  1230  	raw := json.RawMessage(doc)
  1231  	self := newLazyNode(&raw)
  1232  
  1233  	var pd container
  1234  	if doc[0] == '[' {
  1235  		pd = &partialArray{
  1236  			self: self,
  1237  		}
  1238  	} else {
  1239  		pd = &partialDoc{
  1240  			self: self,
  1241  			opts: options,
  1242  		}
  1243  	}
  1244  
  1245  	err := unmarshal(doc, pd)
  1246  
  1247  	if err != nil {
  1248  		return nil, err
  1249  	}
  1250  
  1251  	err = nil
  1252  
  1253  	var accumulatedCopySize int64
  1254  
  1255  	for _, op := range p {
  1256  		switch op.Kind() {
  1257  		case "add":
  1258  			err = p.add(&pd, op, options)
  1259  		case "remove":
  1260  			err = p.remove(&pd, op, options)
  1261  		case "replace":
  1262  			err = p.replace(&pd, op, options)
  1263  		case "move":
  1264  			err = p.move(&pd, op, options)
  1265  		case "test":
  1266  			err = p.test(&pd, op, options)
  1267  		case "copy":
  1268  			err = p.copy(&pd, op, &accumulatedCopySize, options)
  1269  		default:
  1270  			err = fmt.Errorf("Unexpected kind: %s", op.Kind())
  1271  		}
  1272  
  1273  		if err != nil {
  1274  			return nil, err
  1275  		}
  1276  	}
  1277  
  1278  	data, err := json.MarshalEscaped(pd, options.EscapeHTML)
  1279  	if err != nil {
  1280  		return nil, err
  1281  	}
  1282  
  1283  	if indent == "" {
  1284  		return data, nil
  1285  	}
  1286  
  1287  	var buf bytes.Buffer
  1288  	json.Indent(&buf, data, "", indent)
  1289  	return buf.Bytes(), nil
  1290  }
  1291  
  1292  // From http://tools.ietf.org/html/rfc6901#section-4 :
  1293  //
  1294  // Evaluation of each reference token begins by decoding any escaped
  1295  // character sequence.  This is performed by first transforming any
  1296  // occurrence of the sequence '~1' to '/', and then transforming any
  1297  // occurrence of the sequence '~0' to '~'.
  1298  
  1299  var (
  1300  	rfc6901Decoder = strings.NewReplacer("~1", "/", "~0", "~")
  1301  )
  1302  
  1303  func decodePatchKey(k string) string {
  1304  	return rfc6901Decoder.Replace(k)
  1305  }
  1306
View as plain text