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