Line data    Source code

       1             : // Copyright (C) 2020 The Android Open Source Project
       2             : //
       3             : // Licensed under the Apache License, Version 2.0 (the "License");
       4             : // you may not use this file except in compliance with the License.
       5             : // You may obtain a copy of the License at
       6             : //
       7             : // http://www.apache.org/licenses/LICENSE-2.0
       8             : //
       9             : // Unless required by applicable law or agreed to in writing, software
      10             : // distributed under the License is distributed on an "AS IS" BASIS,
      11             : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12             : // See the License for the specific language governing permissions and
      13             : // limitations under the License.
      14             : 
      15             : package com.google.gerrit.server.change;
      16             : 
      17             : import static com.google.common.collect.ImmutableSet.toImmutableSet;
      18             : import static java.util.stream.Collectors.groupingBy;
      19             : 
      20             : import com.google.common.collect.ImmutableMap;
      21             : import com.google.common.collect.ImmutableSet;
      22             : import com.google.common.collect.Streams;
      23             : import com.google.gerrit.entities.Comment;
      24             : import java.util.Comparator;
      25             : import java.util.Map;
      26             : import java.util.PriorityQueue;
      27             : import java.util.Queue;
      28             : import java.util.function.Function;
      29             : 
      30             : /**
      31             :  * Identifier of comment threads.
      32             :  *
      33             :  * <p>Comments are ordered into threads according to their parent relationship indicated via {@link
      34             :  * Comment#parentUuid}. It's possible that two comments refer to the same parent, which especially
      35             :  * happens when two persons reply in parallel. If such branches exist, we merge them into a flat
      36             :  * list taking the comment creation date ({@link Comment#writtenOn} into account (but still
      37             :  * preserving the general parent order). Remaining ties are resolved by using the natural order of
      38             :  * the comment UUID, which is unique.
      39             :  *
      40             :  * @param <T> type of comments in the threads. Can also be {@link Comment} if the threads mix
      41             :  *     comments of different types.
      42             :  */
      43             : public class CommentThreads<T extends Comment> {
      44             : 
      45             :   private final ImmutableMap<String, T> commentPerUuid;
      46             :   private final Map<String, ImmutableSet<T>> childrenPerParent;
      47             : 
      48             :   public CommentThreads(
      49         103 :       ImmutableMap<String, T> commentPerUuid, Map<String, ImmutableSet<T>> childrenPerParent) {
      50         103 :     this.commentPerUuid = commentPerUuid;
      51         103 :     this.childrenPerParent = childrenPerParent;
      52         103 :   }
      53             : 
      54             :   public static <T extends Comment> CommentThreads<T> forComments(Iterable<T> comments) {
      55         103 :     ImmutableMap<String, T> commentPerUuid =
      56         103 :         Streams.stream(comments)
      57         103 :             .distinct()
      58         103 :             .collect(ImmutableMap.toImmutableMap(comment -> comment.key.uuid, Function.identity()));
      59             : 
      60         103 :     Map<String, ImmutableSet<T>> childrenPerParent =
      61         103 :         commentPerUuid.values().stream()
      62         103 :             .filter(comment -> comment.parentUuid != null)
      63         103 :             .collect(groupingBy(comment -> comment.parentUuid, toImmutableSet()));
      64         103 :     return new CommentThreads<>(commentPerUuid, childrenPerParent);
      65             :   }
      66             : 
      67             :   /**
      68             :    * Returns all comments organized into threads.
      69             :    *
      70             :    * <p>Comments appear only once.
      71             :    */
      72             :   public ImmutableSet<CommentThread<T>> getThreads() {
      73         103 :     ImmutableSet<T> roots =
      74         103 :         commentPerUuid.values().stream().filter(this::isRoot).collect(toImmutableSet());
      75             : 
      76         103 :     return buildThreadsOf(roots);
      77             :   }
      78             : 
      79             :   /**
      80             :    * Returns only the comment threads to which the specified comments are a reply.
      81             :    *
      82             :    * <p>If the specified child comments are part of the comments originally provided to {@link
      83             :    * CommentThreads#forComments(Iterable)}, they will also appear in the returned comment threads.
      84             :    * They don't need to be part of the originally provided comments, though, but should refer to one
      85             :    * of these comments via their {@link Comment#parentUuid}. Child comments not referring to any
      86             :    * known comments will be ignored.
      87             :    *
      88             :    * @param childComments comments for which the matching threads should be determined
      89             :    * @return threads to which the provided child comments are a reply
      90             :    */
      91             :   public ImmutableSet<CommentThread<T>> getThreadsForChildren(Iterable<? extends T> childComments) {
      92          66 :     ImmutableSet<T> relevantRoots =
      93          66 :         Streams.stream(childComments)
      94          66 :             .map(this::findRoot)
      95          66 :             .filter(root -> commentPerUuid.containsKey(root.key.uuid))
      96          66 :             .collect(toImmutableSet());
      97          66 :     return buildThreadsOf(relevantRoots);
      98             :   }
      99             : 
     100             :   private T findRoot(T comment) {
     101          22 :     T current = comment;
     102          22 :     while (!isRoot(current)) {
     103           4 :       current = commentPerUuid.get(current.parentUuid);
     104             :     }
     105          22 :     return current;
     106             :   }
     107             : 
     108             :   private boolean isRoot(T current) {
     109          26 :     return current.parentUuid == null || !commentPerUuid.containsKey(current.parentUuid);
     110             :   }
     111             : 
     112             :   private ImmutableSet<CommentThread<T>> buildThreadsOf(ImmutableSet<T> roots) {
     113         103 :     return roots.stream()
     114         103 :         .map(root -> buildCommentThread(root, childrenPerParent))
     115         103 :         .collect(toImmutableSet());
     116             :   }
     117             : 
     118             :   private static <T extends Comment> CommentThread<T> buildCommentThread(
     119             :       T root, Map<String, ImmutableSet<T>> childrenPerParent) {
     120          26 :     CommentThread.Builder<T> commentThread = CommentThread.builder();
     121             :     // Expand comments gradually from the root. If there is more than one child per level, place the
     122             :     // earlier-created child earlier in the thread. Break ties with the UUID to be deterministic.
     123          26 :     Queue<T> unvisited =
     124             :         new PriorityQueue<>(
     125          26 :             Comparator.comparing((T comment) -> comment.writtenOn)
     126          26 :                 .thenComparing(comment -> comment.key.uuid));
     127          26 :     unvisited.add(root);
     128          26 :     while (!unvisited.isEmpty()) {
     129          26 :       T nextComment = unvisited.remove();
     130          26 :       commentThread.addComment(nextComment);
     131          26 :       ImmutableSet<T> children =
     132          26 :           childrenPerParent.getOrDefault(nextComment.key.uuid, ImmutableSet.of());
     133          26 :       unvisited.addAll(children);
     134          26 :     }
     135          26 :     return commentThread.build();
     136             :   }
     137             : }