gerrit.onap Code Review - dcaegen2/services/sdk.git/blob

   1 /*
   2  * ============LICENSE_START====================================
   3  * DCAEGEN2-SERVICES-SDK
   4  * =========================================================
   5  * Copyright (C) 2019 Nokia. All rights reserved.
   6  * =========================================================
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *       http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  * ============LICENSE_END=====================================
  19  */
  20
  21 package org.onap.dcaegen2.services.sdk.rest.services.cbs.client.api.listener;
  22
  23 import io.vavr.Function1;
  24 import io.vavr.collection.HashMap;
  25 import io.vavr.collection.List;
  26 import io.vavr.collection.Map;
  27 import io.vavr.control.Option;
  28 import java.security.MessageDigest;
  29 import java.security.NoSuchAlgorithmException;
  30 import java.util.Arrays;
  31 import java.util.Objects;
  32 import org.jetbrains.annotations.NotNull;
  33
  34 /**
  35  * An immutable <a href="https://en.wikipedia.org/wiki/Merkle_tree" target="_blank">Merkle Tree</a> implementation.
  36  *
  37  * Each node is labelled with a {@code String} label. A path of a node is defined as a list of labels from root to a
  38  * given node.
  39  *
  40  * @author <a href="mailto:piotr.jaszczyk@nokia.com">Piotr Jaszczyk</a>
  41  * @since 1.1.2
  42  */
  43 public final class MerkleTree<V> {
  44
  45     private static final String DEFAULT_DIGEST_ALGORITHM = "SHA-256";
  46     private final ValueSerializer<V> valueSerializer;
  47     private final HashAlgorithm hashAlgorithm;
  48     private final MTNode<V> root;
  49     private final Function1<V, byte[]> hashForValue;
  50
  51     private MerkleTree(
  52             @NotNull ValueSerializer<V> valueSerializer,
  53             @NotNull HashAlgorithm hashAlgorithm,
  54             @NotNull MTNode<V> root) {
  55         this.valueSerializer = Objects.requireNonNull(valueSerializer);
  56         this.hashAlgorithm = Objects.requireNonNull(hashAlgorithm);
  57         this.root = Objects.requireNonNull(root);
  58         hashForValue = valueSerializer.andThen(hashAlgorithm);
  59     }
  60
  61     /**
  62      * Create an empty tree with given serializer and using default digest algorithm as a hash function.
  63      *
  64      * @param serializer a way of serializing a value to array of bytes
  65      * @param <V> type of values kept in a tree
  66      * @return empty tree
  67      */
  68     public static @NotNull <V> MerkleTree<V> emptyWithDefaultDigest(@NotNull ValueSerializer<V> serializer) {
  69         return emptyWithDigest(DEFAULT_DIGEST_ALGORITHM, serializer);
  70     }
  71
  72     /**
  73      * Create an empty tree with given serializer and given digest algorithm used as a hash function.
  74      *
  75      * @param digestAlgorithmName name of a digest algorithm as used by {@link MessageDigest#getInstance(String)}
  76      * @param serializer a way of serializing a value to array of bytes
  77      * @param <V> type of values kept in a tree
  78      * @return empty tree
  79      */
  80     public static @NotNull <V> MerkleTree<V> emptyWithDigest(
  81             @NotNull String digestAlgorithmName,
  82             @NotNull ValueSerializer<V> serializer) {
  83         return emptyWithHashProvider(serializer, messages -> {
  84             final MessageDigest messageDigest = messageDigest(digestAlgorithmName);
  85             messages.forEach(messageDigest::update);
  86             return messageDigest.digest();
  87         });
  88     }
  89
  90     /**
  91      * Create an empty tree with given hash function.
  92      *
  93      * @param serializer a function which serializes values to a byte array
  94      * @param hashAlgorithm a function which calculates a hash of a serialized value
  95      * @param <V> type of values kept in a tree
  96      * @return empty tree
  97      */
  98     public static <V> MerkleTree<V> emptyWithHashProvider(ValueSerializer<V> serializer, HashAlgorithm hashAlgorithm) {
  99         return new MerkleTree<>(serializer, hashAlgorithm, MTNode.empty(hashAlgorithm));
 100     }
 101
 102     private static MessageDigest messageDigest(String digestAlgorithmName) {
 103         try {
 104             return MessageDigest.getInstance(digestAlgorithmName);
 105         } catch (NoSuchAlgorithmException e) {
 106             throw new IllegalArgumentException("Unsupported hash algorithm " + digestAlgorithmName, e);
 107         }
 108     }
 109
 110     /**
 111      * Assigns a value to a given path.
 112      *
 113      * Overrides current value if already exists.
 114      *
 115      * @param value a value to assign
 116      * @param path path of labels from root
 117      * @return an updated tree instance or <code>this</code> if hashes are the same
 118      */
 119     public MerkleTree<V> add(V value, String... path) {
 120         return add(List.of(path), value);
 121     }
 122
 123     /**
 124      * Assigns a value to a given path.
 125      *
 126      * Overrides current value if already exists.
 127      *
 128      * @param path path of labels from root
 129      * @param value a value to assign
 130      * @return an updated tree instance or <code>this</code> if hashes are the same
 131      */
 132     public MerkleTree<V> add(List<String> path, V value) {
 133         final MTNode<V> result = root.addChild(path, MTNode.leaf(hashAlgorithm, hashForValue.apply(value), value));
 134         return Arrays.equals(result.hash(), root.hash())
 135                 ? this
 136                 : new MerkleTree<>(valueSerializer, hashAlgorithm, result);
 137     }
 138
 139
 140     /**
 141      * Gets a value assigned to a given path.
 142      *
 143      * @param path to search for
 144      * @return Some(value) if path exists and contains a value, None otherwise
 145      */
 146     public Option<V> get(String... path) {
 147         return get(List.of(path));
 148     }
 149
 150     /**
 151      * Gets a value assigned to a given path.
 152      *
 153      * @param path to search for
 154      * @return Some(value) if path exists and contains a value, None otherwise
 155      */
 156     public Option<V> get(List<String> path) {
 157         return root.findNode(path).flatMap(MTNode::value);
 158     }
 159
 160     /**
 161      * Checks if nodes under given path are the same in {@code this} and {@code other} tree.
 162      *
 163      * @param other a tree to compare with
 164      * @param path a path to a subtree to compare
 165      * @return true if hashes are the same, false otherwise
 166      */
 167     public boolean isSame(MerkleTree<V> other, String... path) {
 168         return isSame(List.of(path), other);
 169     }
 170
 171     /**
 172      * Checks if nodes under given path are the same in {@code this} and {@code other} tree.
 173      *
 174      * @param other a tree to compare with
 175      * @param path a path to a subtree to compare
 176      * @return true if hashes are the same, false otherwise
 177      */
 178     public boolean isSame(List<String> path, MerkleTree<V> other) {
 179         final byte[] oldHash = other.hashOf(path);
 180         final byte[] curHash = hashOf(path);
 181         return Arrays.equals(oldHash, curHash);
 182     }
 183
 184     /**
 185      * Returns a hash of a node under given path.
 186      *
 187      * @param path a path of a node to check
 188      * @return a hash or empty array if node does not exist
 189      */
 190     public byte[] hashOf(List<String> path) {
 191         return root
 192                 .findNode(path)
 193                 .map(node -> node.hash().clone())
 194                 .getOrElse(() -> new byte[0]);
 195     }
 196
 197     /**
 198      * Returns a hash of a node under given path.
 199      *
 200      * @param path a path of a node to check
 201      * @return a hash or empty array if node does not exist
 202      */
 203     public byte[] hashOf(String... path) {
 204         return hashOf(List.of(path));
 205     }
 206
 207     /**
 208      * Returns a subtree with given node as a root.
 209      *
 210      * @param path a path of a node to be a subtree root
 211      * @return Some(subtree) if path exists, None otherwise
 212      */
 213     public Option<MerkleTree<V>> subtree(List<String> path) {
 214         return root.findNode(path).map(node -> new MerkleTree<>(valueSerializer, hashAlgorithm, node));
 215     }
 216
 217     /**
 218      * Returns a subtree with given node as a root.
 219      *
 220      * @param path a path of a node to be a subtree root
 221      * @return Some(subtree) if path exists, None otherwise
 222      */
 223     public Option<MerkleTree<V>> subtree(String... path) {
 224         return subtree(List.of(path));
 225     }
 226
 227     /**
 228      * Hash of a root node.
 229      *
 230      * @return a copy of root node's hash
 231      */
 232     public byte[] hash() {
 233         return root.hash().clone();
 234     }
 235
 236     @Override
 237     public String toString() {
 238         return root.toString();
 239     }
 240
 241     @Override
 242     public boolean equals(Object o) {
 243         if (this == o) {
 244             return true;
 245         }
 246         if (o == null || getClass() != o.getClass()) {
 247             return false;
 248         }
 249         MerkleTree<?> that = (MerkleTree<?>) o;
 250         return Objects.equals(root, that.root);
 251     }
 252
 253     @Override
 254     public int hashCode() {
 255         return Objects.hash(root);
 256     }
 257 }
 258
 259 final class MTNode<V> {
 260
 261     private final byte[] hash;
 262     private final Option<V> value;
 263     private final Map<String, MTNode<V>> children;
 264     private final HashAlgorithm hashAlgorithm;
 265
 266     static <V> MTNode<V> empty(HashAlgorithm hashAlgorithm) {
 267         return new MTNode<>(hashAlgorithm, new byte[0], Option.none(), HashMap.empty());
 268     }
 269
 270     static <V> MTNode<V> leaf(HashAlgorithm hashAlgorithm, byte[] hash, V value) {
 271         return new MTNode<>(hashAlgorithm, hash, Option.of(value), HashMap.empty());
 272     }
 273
 274     private MTNode(
 275             HashAlgorithm hashAlgorithm,
 276             byte[] hash,
 277             Option<V> value,
 278             Map<String, MTNode<V>> children) {
 279         this.hashAlgorithm = hashAlgorithm;
 280         this.hash = hash.clone();
 281         this.value = value;
 282         this.children = children;
 283     }
 284
 285     MTNode<V> addChild(final List<String> path, final MTNode<V> child) {
 286         if (path.isEmpty()) {
 287             return child;
 288         } else {
 289             String label = path.head();
 290             MTNode<V> newChild = children.get(label).fold(
 291                     () -> MTNode.<V>empty(hashAlgorithm).addChild(path.tail(), child),
 292                     node -> node.addChild(path.tail(), child)
 293             );
 294             return addChild(label, newChild);
 295         }
 296     }
 297
 298     Option<V> value() {
 299         return value;
 300     }
 301
 302     Option<MTNode<V>> findNode(List<String> path) {
 303         return path.headOption().fold(
 304                 () -> Option.of(this),
 305                 head -> children.get(head).flatMap(child -> child.findNode(path.tail()))
 306         );
 307     }
 308
 309     byte[] hash() {
 310         return hash;
 311     }
 312
 313     private MTNode<V> addChild(String label, MTNode<V> child) {
 314         final Map<String, MTNode<V>> newChildren = children.put(label, child);
 315         byte[] newHash = composeHashes(newChildren.iterator(this::hashForChild));
 316         return Arrays.equals(newHash, hash) ? this : new MTNode<>(
 317                 hashAlgorithm,
 318                 newHash,
 319                 value,
 320                 newChildren
 321         );
 322     }
 323
 324     private byte[] hashForChild(String label, MTNode<V> child) {
 325         return composeHashes(List.of(label.getBytes(), child.hash()));
 326     }
 327
 328     private byte[] composeHashes(Iterable<byte[]> hashes) {
 329         return hashAlgorithm.apply(hashes);
 330     }
 331
 332     @Override
 333     public String toString() {
 334         return "(\"" + value.map(Object::toString).getOrElse("") + "\" ["
 335                 + children.map(entry -> entry._1 + "=" + entry._2).mkString(", ")
 336                 + "])";
 337     }
 338
 339     @Override
 340     public boolean equals(Object o) {
 341         if (this == o) {
 342             return true;
 343         }
 344         if (o == null || getClass() != o.getClass()) {
 345             return false;
 346         }
 347         MTNode<?> mtNode = (MTNode<?>) o;
 348         return Arrays.equals(hash, mtNode.hash);
 349     }
 350
 351     @Override
 352     public int hashCode() {
 353         return Arrays.hashCode(hash);
 354     }
 355 }