// Copyright 2014 Google Inc. 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.HashMultimap;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.MapMaker;
import com.google.common.collect.Multimaps;
import com.google.common.collect.SetMultimap;
import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
import com.google.devtools.build.lib.events.EventHandler;
import com.google.devtools.build.lib.packages.AggregatingAttributeMapper;
import com.google.devtools.build.lib.packages.Attribute;
import com.google.devtools.build.lib.packages.AttributeMap;
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.Package;
import com.google.devtools.build.lib.packages.PackageGroup;
import com.google.devtools.build.lib.packages.Rule;
import com.google.devtools.build.lib.packages.Target;
import com.google.devtools.build.lib.pkgcache.PackageProvider;
import com.google.devtools.build.lib.pkgcache.TargetEdgeObserver;
import com.google.devtools.build.lib.syntax.Label;
import com.google.devtools.build.lib.util.BinaryPredicate;
import java.util.Collection;
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 boolean visitSubincludes = true;
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
&& visitSubincludes == lastVisitation.visitSubincludes;
}
}
/*
* 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 can happen in two
* different ways depending on whether Python preprocessing is in effect or
* not.
*
* If there is no Python preprocessing:
*
* 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.
*
* If there is Python preprocessing, events are a bit more complicated. In
* this case, the real work happens on the thread the Python preprocessor is
* called from, but in a bit more convoluted way: a new thread is spawned by
* to handle the input from the Python process and
* the output to the Python process is handled on the main thread. The reading
* thread parses requests from the preprocessor, and passes them using a queue
* to the writing thread (that is, the main thread), so that we can do the
* work there. This is important because this way, we don't have any work that
* we need to interrupt in a thread that is not spawned by us. So:
*
* 1. The interrupted state of the main thread is set.
*
* 2. This results in an InterruptedException during the execution of the task
* in PythonStdinInputStream.getNextMessage().
*
* 3. We exit from RequestParser.Request.run() prematurely, set a flag to
* signal that we were interrupted, and throw an InterruptedIOException.
*
* 4. The Python child process and reading thread are terminated.
*
* 5. Based on the flag we set in step 3, we realize that the termination was
* due to an interruption, and an InterruptedException is thrown. This can
* either raise an AbnormalTerminationException, or make Command.execute()
* return normally, so we check for both cases.
*
* 6. This InterruptedException causes the loading of the package to terminate
* prematurely.
*
* Life is not simple.
*/
private final PackageProvider packageProvider;
private final BinaryPredicate edgeFilter;
private final SetMultimap visitedMap =
Multimaps.synchronizedSetMultimap(HashMultimap.create());
private final ConcurrentMap