1/*
2 * Copyright (c) Facebook, Inc. and its affiliates.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <folly/json_patch.h>
18
19#include <glog/logging.h>
20
21#include <folly/container/Enumerate.h>
22
23namespace {
24using folly::StringPiece;
25// JSON patch operation names
26constexpr StringPiece kOperationTest = "test";
27constexpr StringPiece kOperationRemove = "remove";
28constexpr StringPiece kOperationAdd = "add";
29constexpr StringPiece kOperationReplace = "replace";
30constexpr StringPiece kOperationMove = "move";
31constexpr StringPiece kOperationCopy = "copy";
32// field tags in JSON patch
33constexpr StringPiece kOpTag = "op";
34constexpr StringPiece kValueTag = "value";
35constexpr StringPiece kPathTag = "path";
36constexpr StringPiece kFromTag = "from";
37} // namespace
38
39namespace folly {
40
41// static
42Expected<json_patch, json_patch::parse_error> json_patch::try_parse(
43 dynamic const& obj) noexcept {
44 using err_code = parse_error_code;
45
46 json_patch patch;
47 if (!obj.isArray()) {
48 return makeUnexpected(parse_error{err_code::invalid_shape, &obj});
49 }
50 for (auto const& elem : obj) {
51 if (!elem.isObject()) {
52 return makeUnexpected(parse_error{err_code::invalid_shape, &elem});
53 }
54 auto const* op_ptr = elem.get_ptr(kOpTag);
55 if (!op_ptr) {
56 return makeUnexpected(parse_error{err_code::missing_op, &elem});
57 }
58 if (!op_ptr->isString()) {
59 return makeUnexpected(parse_error{err_code::malformed_op, &elem});
60 }
61 auto const op_str = op_ptr->asString();
62 patch_operation op;
63
64 // extract 'from' attribute
65 {
66 auto const* from_ptr = elem.get_ptr(kFromTag);
67 if (from_ptr) {
68 if (!from_ptr->isString()) {
69 return makeUnexpected(parse_error{err_code::invalid_shape, &elem});
70 }
71 auto json_ptr = json_pointer::try_parse(from_ptr->asString());
72 if (!json_ptr.hasValue()) {
73 return makeUnexpected(
74 parse_error{err_code::malformed_from_attr, &elem});
75 }
76 op.from = json_ptr.value();
77 }
78 }
79
80 // extract 'path' attribute
81 {
82 auto const* path_ptr = elem.get_ptr(kPathTag);
83 if (!path_ptr) {
84 return makeUnexpected(parse_error{err_code::missing_path_attr, &elem});
85 }
86 if (!path_ptr->isString()) {
87 return makeUnexpected(
88 parse_error{err_code::malformed_path_attr, &elem});
89 }
90 auto const json_ptr = json_pointer::try_parse(path_ptr->asString());
91 if (!json_ptr.hasValue()) {
92 return makeUnexpected(
93 parse_error{err_code::malformed_path_attr, &elem});
94 }
95 op.path = json_ptr.value();
96 }
97
98 // extract 'value' attribute
99 {
100 auto const* val_ptr = elem.get_ptr(kValueTag);
101 if (val_ptr) {
102 op.value = *val_ptr;
103 }
104 }
105
106 // check mandatory attributes - different per operation
107 // NOTE: per RFC, the surplus attributes (e.g. 'from' with 'add')
108 // should be simply ignored
109
110 using op_code = patch_operation_code;
111
112 if (op_str == kOperationTest) {
113 if (!op.value) {
114 return makeUnexpected(parse_error{err_code::missing_value_attr, &elem});
115 }
116 op.op_code = op_code::test;
117 } else if (op_str == kOperationRemove) {
118 op.op_code = op_code::remove;
119 } else if (op_str == kOperationAdd) {
120 if (!op.value) {
121 return makeUnexpected(parse_error{err_code::missing_value_attr, &elem});
122 }
123 op.op_code = op_code::add;
124 } else if (op_str == kOperationReplace) {
125 if (!op.value) {
126 return makeUnexpected(parse_error{err_code::missing_value_attr, &elem});
127 }
128 op.op_code = op_code::replace;
129 } else if (op_str == kOperationMove) {
130 if (!op.from) {
131 return makeUnexpected(parse_error{err_code::missing_from_attr, &elem});
132 }
133 // is from a proper prefix to path?
134 if (op.from->is_prefix_of(op.path)) {
135 return makeUnexpected(
136 parse_error{err_code::overlapping_pointers, &elem});
137 }
138 op.op_code = op_code::move;
139 } else if (op_str == kOperationCopy) {
140 if (!op.from) {
141 return makeUnexpected(parse_error{err_code::missing_from_attr, &elem});
142 }
143 op.op_code = op_code::copy;
144 }
145
146 if (op.op_code != op_code::invalid) {
147 patch.ops_.emplace_back(std::move(op));
148 } else {
149 return makeUnexpected(parse_error{err_code::unknown_op, &elem});
150 }
151 }
152 return patch;
153}
154
155std::vector<json_patch::patch_operation> const& json_patch::ops() const {
156 return ops_;
157}
158
159namespace {
160// clang-format off
161Expected<Unit, json_patch::patch_application_error_code>
162// clang-format on
163do_remove(dynamic::resolved_json_pointer<dynamic>& ptr) {
164 using error_code = json_patch::patch_application_error_code;
165
166 if (!ptr.hasValue()) {
167 return folly::makeUnexpected(error_code::path_not_found);
168 }
169
170 auto parent = ptr->parent;
171
172 if (!parent) {
173 return folly::makeUnexpected(error_code::other);
174 }
175
176 if (parent->isObject()) {
177 parent->erase(ptr->parent_key);
178 return unit;
179 }
180
181 if (parent->isArray()) {
182 parent->erase(parent->begin() + ptr->parent_index);
183 return unit;
184 }
185
186 return folly::makeUnexpected(error_code::other);
187}
188
189// clang-format off
190Expected<Unit, json_patch::patch_application_error_code>
191// clang-format on
192do_add(
193 dynamic::resolved_json_pointer<dynamic>& ptr,
194 const dynamic& value,
195 const std::string& last_token) {
196 using app_err_code = json_patch::patch_application_error_code;
197 using res_err_code = dynamic::json_pointer_resolution_error_code;
198
199 // element found: see if parent is object or array
200 if (ptr.hasValue()) {
201 // root element, or key in object - replace (per RFC)
202 if (ptr->parent == nullptr || ptr->parent->isObject()) {
203 *ptr->value = value;
204 }
205 // valid index in array: insert at index and shift right
206 if (ptr->parent && ptr->parent->isArray()) {
207 ptr->parent->insert(ptr->parent->begin() + ptr->parent_index, value);
208 }
209 } else {
210 // see if we can add value, based on pointer resolution state
211 switch (ptr.error().error_code) {
212 // key not found. can only happen in object - add new key-value
213 case res_err_code::key_not_found: {
214 DCHECK(ptr.error().context->isObject());
215 ptr.error().context->insert(last_token, value);
216 break;
217 }
218 // special '-' index in array - do append operation
219 case res_err_code::append_requested: {
220 DCHECK(ptr.error().context->isArray());
221 ptr.error().context->push_back(value);
222 break;
223 }
224 case res_err_code::other:
225 case res_err_code::index_out_of_bounds:
226 case res_err_code::index_not_numeric:
227 case res_err_code::index_has_leading_zero:
228 case res_err_code::element_not_object_or_array:
229 case res_err_code::json_pointer_out_of_bounds:
230 default:
231 return folly::makeUnexpected(app_err_code::other);
232 }
233 }
234 return unit;
235}
236} // namespace
237
238// clang-format off
239Expected<Unit, json_patch::patch_application_error>
240// clang-format on
241json_patch::apply(dynamic& obj) {
242 using op_code = patch_operation_code;
243 using error_code = patch_application_error_code;
244 using error = patch_application_error;
245
246 for (auto it : enumerate(ops_)) {
247 auto const index = it.index;
248 auto const& op = *it;
249 auto resolved_path = obj.try_get_ptr(op.path);
250
251 switch (op.op_code) {
252 case op_code::test:
253 if (!resolved_path.hasValue()) {
254 return folly::makeUnexpected(
255 error{error_code::path_not_found, index});
256 }
257 if (*resolved_path->value != *op.value) {
258 return folly::makeUnexpected(error{error_code::test_failed, index});
259 }
260 break;
261 case op_code::remove: {
262 auto ret = do_remove(resolved_path);
263 if (ret.hasError()) {
264 return makeUnexpected(error{ret.error(), index});
265 }
266 break;
267 }
268 case op_code::add: {
269 DCHECK(op.value.hasValue());
270 auto ret = do_add(resolved_path, *op.value, op.path.tokens().back());
271 if (ret.hasError()) {
272 return makeUnexpected(error{ret.error(), index});
273 }
274 break;
275 }
276 case op_code::replace: {
277 if (resolved_path.hasValue()) {
278 *resolved_path->value = *op.value;
279 } else {
280 return folly::makeUnexpected(
281 error{error_code::path_not_found, index});
282 }
283 break;
284 }
285 case op_code::move: {
286 DCHECK(op.from.hasValue());
287 auto resolved_from = obj.try_get_ptr(*op.from);
288 if (!resolved_from.hasValue()) {
289 return makeUnexpected(error{error_code::from_not_found, index});
290 }
291 {
292 auto ret = do_add(
293 resolved_path, *resolved_from->value, op.path.tokens().back());
294 if (ret.hasError()) {
295 return makeUnexpected(error{ret.error(), index});
296 }
297 }
298 {
299 auto ret = do_remove(resolved_from);
300 if (ret.hasError()) {
301 return makeUnexpected(error{ret.error(), index});
302 }
303 }
304 break;
305 }
306 case op_code::copy: {
307 DCHECK(op.from.hasValue());
308 auto const resolved_from = obj.try_get_ptr(*op.from);
309 if (!resolved_from.hasValue()) {
310 return makeUnexpected(error{error_code::from_not_found, index});
311 }
312 {
313 DCHECK(!op.path.tokens().empty());
314 auto ret = do_add(
315 resolved_path, *resolved_from->value, op.path.tokens().back());
316 if (ret.hasError()) {
317 return makeUnexpected(error{ret.error(), index});
318 }
319 }
320 break;
321 }
322 case op_code::invalid: {
323 DCHECK(false);
324 return makeUnexpected(error{error_code::other, index});
325 }
326 }
327 }
328 return unit;
329}
330
331} // namespace folly
332