1 /* 2 * Copyright 2017 LINE Corporation 3 * 4 * LINE Corporation licenses this file to you under the Apache License, 5 * version 2.0 (the "License"); you may not use this file except in compliance 6 * with the License. You may obtain a copy of the License at: 7 * 8 * https://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, WITHOUT 12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 13 * License for the specific language governing permissions and limitations 14 * under the License. 15 */ 16 /* 17 * Copyright (c) 2014, Francis Galiegue (fgaliegue@gmail.com) 18 * 19 * This software is dual-licensed under: 20 * 21 * - the Lesser General Public License (LGPL) version 3.0 or, at your option, any 22 * later version; 23 * - the Apache Software License (ASL) version 2.0. 24 * 25 * The text of this file and of both licenses is available at the root of this 26 * project or, if you have the jar distribution, in directory META-INF/, under 27 * the names LGPL-3.0.txt and ASL-2.0.txt respectively. 28 * 29 * Direct link to the sources: 30 * 31 * - LGPL 3.0: https://www.gnu.org/licenses/lgpl-3.0.txt 32 * - ASL 2.0: https://www.apache.org/licenses/LICENSE-2.0.txt 33 */ 34 35 package com.linecorp.centraldogma.internal.jsonpatch; 36 37 import java.util.Iterator; 38 import java.util.Map; 39 import java.util.Set; 40 41 import com.fasterxml.jackson.databind.JsonNode; 42 import com.fasterxml.jackson.databind.node.JsonNodeType; 43 import com.google.common.base.Equivalence; 44 import com.google.common.collect.Sets; 45 46 /** 47 * An {@link Equivalence} strategy for JSON Schema equality. 48 * 49 * <p>{@link JsonNode} does a pretty good job of obeying the {@link 50 * Object#equals(Object) equals()}/{@link Object#hashCode() hashCode()} 51 * contract. And in fact, it does it too well for JSON Schema.</p> 52 * 53 * <p>For instance, it considers numeric nodes {@code 1} and {@code 1.0} to be 54 * different nodes, which is true. But some IETF RFCs and drafts (among them, 55 * JSON Schema and JSON Patch) mandate that numeric JSON values be considered 56 * equal if their mathematical value is the same. This class implements this 57 * kind of equality.</p> 58 */ 59 final class JsonNumEquals extends Equivalence<JsonNode> { 60 61 private static final Equivalence<JsonNode> INSTANCE = new JsonNumEquals(); 62 63 public static Equivalence<JsonNode> getInstance() { 64 return INSTANCE; 65 } 66 67 private JsonNumEquals() {} 68 69 @Override 70 protected boolean doEquivalent(final JsonNode a, final JsonNode b) { 71 /* 72 * If both are numbers, delegate to the helper method 73 */ 74 if (a.isNumber() && b.isNumber()) { 75 return numEquals(a, b); 76 } 77 78 final JsonNodeType typeA = a.getNodeType(); 79 final JsonNodeType typeB = b.getNodeType(); 80 81 /* 82 * If they are of different types, no dice 83 */ 84 if (typeA != typeB) { 85 return false; 86 } 87 88 /* 89 * For all other primitive types than numbers, trust JsonNode 90 */ 91 if (!a.isContainerNode()) { 92 return a.equals(b); 93 } 94 95 /* 96 * OK, so they are containers (either both arrays or objects due to the 97 * test on types above). They are obviously not equal if they do not 98 * have the same number of elements/members. 99 */ 100 if (a.size() != b.size()) { 101 return false; 102 } 103 104 /* 105 * Delegate to the appropriate method according to their type. 106 */ 107 return typeA == JsonNodeType.ARRAY ? arrayEquals(a, b) : objectEquals(a, b); 108 } 109 110 @Override 111 protected int doHash(final JsonNode t) { 112 /* 113 * If this is a numeric node, we want the same hashcode for the same 114 * mathematical values. Go with double, its range is good enough for 115 * 99+% of use cases. 116 */ 117 if (t.isNumber()) { 118 return Double.valueOf(t.doubleValue()).hashCode(); 119 } 120 121 /* 122 * If this is a primitive type (other than numbers, handled above), 123 * delegate to JsonNode. 124 */ 125 if (!t.isContainerNode()) { 126 return t.hashCode(); 127 } 128 129 /* 130 * The following hash calculations work, yes, but they are poor at best. 131 * And probably slow, too. 132 * 133 * TODO: try and figure out those hash classes from Guava 134 */ 135 int ret = 0; 136 137 /* 138 * If the container is empty, just return 139 */ 140 if (t.size() == 0) { 141 return ret; 142 } 143 144 /* 145 * Array 146 */ 147 if (t.isArray()) { 148 for (final JsonNode element : t) { 149 ret = 31 * ret + doHash(element); 150 } 151 return ret; 152 } 153 154 /* 155 * Not an array? An object. 156 */ 157 final Iterator<Map.Entry<String, JsonNode>> iterator = t.fields(); 158 159 Map.Entry<String, JsonNode> entry; 160 161 while (iterator.hasNext()) { 162 entry = iterator.next(); 163 ret = 31 * ret + (entry.getKey().hashCode() ^ doHash(entry.getValue())); 164 } 165 166 return ret; 167 } 168 169 private static boolean numEquals(final JsonNode a, final JsonNode b) { 170 /* 171 * If both numbers are integers, delegate to JsonNode. 172 */ 173 if (a.isIntegralNumber() && b.isIntegralNumber()) { 174 return a.equals(b); 175 } 176 177 /* 178 * Otherwise, compare decimal values. 179 */ 180 return a.decimalValue().compareTo(b.decimalValue()) == 0; 181 } 182 183 private boolean arrayEquals(final JsonNode a, final JsonNode b) { 184 /* 185 * We are guaranteed here that arrays are the same size. 186 */ 187 final int size = a.size(); 188 189 for (int i = 0; i < size; i++) { 190 if (!doEquivalent(a.get(i), b.get(i))) { 191 return false; 192 } 193 } 194 195 return true; 196 } 197 198 private boolean objectEquals(final JsonNode a, final JsonNode b) { 199 /* 200 * Grab the key set from the first node 201 */ 202 final Set<String> keys = Sets.newHashSet(a.fieldNames()); 203 204 /* 205 * Grab the key set from the second node, and see if both sets are the 206 * same. If not, objects are not equal, no need to check for children. 207 */ 208 final Set<String> set = Sets.newHashSet(b.fieldNames()); 209 if (!set.equals(keys)) { 210 return false; 211 } 212 213 /* 214 * Test each member individually. 215 */ 216 for (final String key : keys) { 217 if (!doEquivalent(a.get(key), b.get(key))) { 218 return false; 219 } 220 } 221 222 return true; 223 } 224 }