src/main/java/com/google/devtools/build/lib/remote/util/ConcurrentPathTrie.java

// Copyright 2023 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.lib.remote.util;

import static com.google.common.base.Preconditions.checkArgument;

import com.google.devtools.build.lib.vfs.PathFragment;
import java.util.Iterator;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Stores a collection of paths as a trie safe for concurrent read/write access.
 *
 * <p>All paths must be relative and non-empty. Once a path has been added it cannot be removed.
 */
public final class ConcurrentPathTrie {

  private enum Match {
    NONE,
    EXACT,
    PREFIX
  }

  private static final class Node {
    final ConcurrentHashMap<String, Node> tab = new ConcurrentHashMap<>();
    Match state = Match.NONE;
  }

  private final Node root = new Node();

  /** Returns whether the trie contains the given path. */
  public boolean contains(PathFragment path) {
    checkValid(path);

    Node node = root;
    Iterator<String> segmentIterator = path.segments().iterator();

    while (segmentIterator.hasNext()) {
      String segment = segmentIterator.next();
      boolean isLast = !segmentIterator.hasNext();

      node = node.tab.get(segment);

      if (node == null) {
        // No match.
        return false;
      }

      if (node.state == Match.PREFIX) {
        // Prefix match.
        return true;
      }

      if (isLast && node.state == Match.EXACT) {
        // Exact match.
        return true;
      }
    }

    // Reached end of input path without a match.
    return false;
  }

  /** Adds the given path to the trie. */
  public void add(PathFragment path) {
    addInternal(path, false);
  }

  /** Adds the set of paths with the given prefix to the trie. */
  public void addPrefix(PathFragment path) {
    addInternal(path, true);
  }

  private void addInternal(PathFragment path, boolean asPrefix) {
    checkValid(path);

    Node node = root;
    Iterator<String> segmentIterator = path.segments().iterator();

    while (segmentIterator.hasNext()) {
      String segment = segmentIterator.next();
      boolean isLast = !segmentIterator.hasNext();

      node =
          node.tab.compute(
              segment,
              (unusedKey, val) -> {
                if (val == null) {
                  val = new Node();
                }
                if (isLast) {
                  if (asPrefix) {
                    // Add as prefix match.
                    val.state = Match.PREFIX;
                  } else {
                    // Add as exact match.
                    val.state = Match.EXACT;
                  }
                }
                return val;
              });
    }
  }

  private static void checkValid(PathFragment path) {
    checkArgument(
        !path.isAbsolute() && !path.isEmpty(),
        "ConcurrentPathTrie only accepts relative non-empty paths");
  }
}