// Copyright 2014 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.query2;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Throwables;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMultimap;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
import com.google.devtools.build.lib.concurrent.ErrorClassifier;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
import com.google.devtools.build.lib.events.ExtendedEventHandler;
import com.google.devtools.build.lib.packages.AggregatingAttributeMapper;
import com.google.devtools.build.lib.packages.AspectDefinition;
import com.google.devtools.build.lib.packages.Attribute;
import com.google.devtools.build.lib.packages.BuildType;
import com.google.devtools.build.lib.packages.DependencyFilter;
import com.google.devtools.build.lib.packages.InputFile;
import com.google.devtools.build.lib.packages.NoSuchThingException;
import com.google.devtools.build.lib.packages.OutputFile;
import com.google.devtools.build.lib.packages.PackageGroup;
import com.google.devtools.build.lib.packages.Rule;
import com.google.devtools.build.lib.packages.RuleClass;
import com.google.devtools.build.lib.packages.Target;
import com.google.devtools.build.lib.pkgcache.TargetEdgeObserver;
import com.google.devtools.build.lib.pkgcache.TargetProvider;
import java.util.Collection;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
/**
*
Visit the transitive closure of a label. Primarily used to "fault in"
* packages to the packageProvider and ensure the necessary targets exists, in
* advance of the configuration step, which is intolerant of missing
* packages/targets.
*
*
LabelVisitor loads packages concurrently where possible, to increase I/O
* parallelism. However, the public interface is not thread-safe: calls to
* public methods should not be made concurrently.
*
*
LabelVisitor is stateful: It remembers the previous visitation and can
* check its validity on subsequent calls to sync() instead of doing the normal
* visitation.
*
*
TODO(bazel-team): (2009) a small further optimization could be achieved if we
* create tasks at the package (not individual label) level, since package
* loading is the expensive step. This would require additional bookkeeping to
* maintain the list of labels that we need to visit once a package becomes
* available. Profiling suggests that there is still a potential benefit to be
* gained: when the set of packages is known a-priori, loading a set of packages
* that took 20 seconds can be done under 5 in the sequential case or 7 in the
* current (parallel) case.
*
*
Concurrency
*
*
The sync() methods of this class is thread-compatible. The accessor
* ({@link #hasVisited} and similar must not be called until the concurrent phase
* is over, i.e. all external calls to visit() methods have completed.
*/
final class LabelVisitor {
/**
* Attributes of a visitation which determine whether it is up-to-date or not.
*/
private class VisitationAttributes {
private Collection targetsToVisit;
private boolean success = false;
private int maxDepth = 0;
/**
* Returns true if and only if this visitation attribute is still up-to-date.
*/
boolean current() {
return targetsToVisit.equals(lastVisitation.targetsToVisit)
&& maxDepth <= lastVisitation.maxDepth;
}
}
/*
* Interrupts during the loading phase ===================================
*
* Bazel can be interrupted in the middle of the loading phase. The mechanics
* of this are far from trivial, so there is an explanation of how they are
* supposed to work. For a description how the same thing works in the
* execution phase, see ParallelBuilder.java .
*
* The sequence of events that happen when the user presses Ctrl-C is the
* following:
*
* 1. A SIGINT gets delivered to the Bazel client process.
*
* 2. The client process delivers the SIGINT to the server process.
*
* 3. The interruption state of the main thread is set to true.
*
* 4. Sooner or later, this results in an InterruptedException being thrown.
* Usually this takes place because the main thread is interrupted during
* AbstractQueueVisitor.awaitTermination(). The only exception to this is when
* the interruption occurs during the loading of a package of a label
* specified on the command line; in this case, the InterruptedException is
* thrown during the loading of an individual package (see below where this
* can occur)
*
* 5. The main thread calls ThreadPoolExecutor.shutdown(), which in turn
* interrupts every worker thread. Then the main thread waits for their
* termination.
*
* 6. An InterruptedException is thrown during the loading of an individual
* package in the worker threads.
*
* 7. All worker threads terminate.
*
* 8. An InterruptedException is thrown from
* AbstractQueueVisitor.awaitTermination()
*
* 9. This exception causes the execution of the currently running command to
* terminate prematurely.
*
* The interruption of the loading of an individual package happens as follow:
*
* 1. We periodically check the interruption state of the thread in
* UnixGlob.reallyGlob(). If it is interrupted, an InterruptedException is
* thrown.
*
* 2. The stack is unwound until we are out of the part of the call stack
* responsible for package loading. This either means that the worker thread
* terminates or that the label parsing terminates if the package that is
* being loaded was specified on the command line.
*/
private final TargetProvider targetProvider;
private final DependencyFilter edgeFilter;
private final ConcurrentMap