aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/main/java/com/google/devtools/build/lib/query2/engine
Commit message (Collapse)AuthorAge
* Add method getRdepsUnboundedInUniverseParallel to StremableQueryEnvironmentGravatar Googler2017-09-04
| | | | | RELNOTES: None PiperOrigin-RevId: 167335614
* Change WalkableGraphFactory#prepareAndGet to take multiple SkyKeys as graph ↵Gravatar Googler2017-08-17
| | | | | | | | | | roots It also changes a few accessors of utility methods in Skyframe library. It refactors the QueryExpressionMapper to use a general QueryExpressionVisitor. RELNOTES: None PiperOrigin-RevId: 165534908
* Introduce the 'siblings' query function.Gravatar nharmata2017-08-14
| | | | | | RELNOTES[NEW]: There is now a 'siblings' query function. See the query documentation for more details. PiperOrigin-RevId: 165010653
* Generalize some of methods in TargetPattern, PrepareDepsOfPatternValue, and ↵Gravatar nharmata2017-07-26
| | | | | | | RecursivePackageProvider dealing with the concept of "excluded directories". RELNOTES: None PiperOrigin-RevId: 163074794
* Automated conversion to Java 8Gravatar laurentlb2017-06-30
| | | | | | | With a few manual fixes for readability. RELNOTES: None. PiperOrigin-RevId: 160582556
* Refactor SkyQueryEnvironment to allow preprocessing or postprocessing targetsGravatar Googler2017-06-27
| | | | | | | | Refactor SkyQueryEnvironment and a few other query helpers to make it easier to work with targets. RELNOTES: None PiperOrigin-RevId: 160165398
* In the Blaze Query implementation, use Set and Map implementations backed by ↵Gravatar nharmata2017-06-22
| | | | | | | the same KeyExtractor used that the Uniquifier implementation uses. This fixes a hypothetical issue where we were previously relying on Target#equals/hashCode. RELNOTES: None PiperOrigin-RevId: 159741545
* Ban the combination of buildfiles/loadfiles and --output=location.Gravatar nharmata2017-06-19
| | | | | | RELNOTES[INC]: The --output=location flag to 'bazel query' cannot be used with query expressions that involve the 'buildfiles' or 'loadfiles' operators. This also applies to 'genquery' rules. PiperOrigin-RevId: 159259061
* Don't call function names keyword in the query reference because they are not.Gravatar lberki2017-06-13
| | | | | RELNOTES: None. PiperOrigin-RevId: 158721043
* Don't throw runtime exception on interruption - since we know the future is ↵Gravatar Googler2017-05-26
| | | | | | already done, we should leave the thread in an interrupted state and proceed. This fixes a blaze crash when a 'genquery' execution is interrupted at the right time. PiperOrigin-RevId: 157000269
* Have QueryExpressionMapper#compose take arbitrary number of mappersGravatar Googler2017-05-04
| | | | | | | AttrFunction and LabelsFunction are also made public. RELNOTES: None PiperOrigin-RevId: 155108260
* Global cleanup change.Gravatar Googler2017-03-23
| | | | | | -- PiperOrigin-RevId: 151019690 MOS_MIGRATED_REVID=151019690
* Fix inadvertent performance regression introduced by the recent rewrite of ↵Gravatar Nathan Harmata2017-03-14
| | | | | | | | | | | | | | | | | | 'blaze query'. The "streaming" callbacks used by some query functions, e.g. 'deps', make calls to QueryEnvironment#buildTransitiveClosure. For a cold blaze server, these calls do package loading via LabelVisitor (which calls into Skyframe via a top-level #evaluate call). So we'd prefer a single massive call which can make full use of blaze's loading-phase parallelism via Skyframe over a bunch of sequential small calls. For a hot blaze server, there are two problems: (1) LabelVisitor's meager up-to-date check isn't useful (as in we cannot reuse old visitations) when we do a whole bunch of small visitations instead of one massive one. (2) The actual work of the LabelVisitor (building up a portion of a temporary graph) isn't being effectively parallelized when we do it sequentially in small chunks. This issue is yet another subtle reason why the old BlazeQueryEnvironment#eval made sense (and why it was unfortunately not compatible with the streaming query evaluation model from the beginning). -- PiperOrigin-RevId: 150081619 MOS_MIGRATED_REVID=150081619
* Description redacted.Gravatar Nathan Harmata2017-03-09
| | | | | | -- PiperOrigin-RevId: 149585165 MOS_MIGRATED_REVID=149585165
* Fix bug with streaming bounded deps/allrdeps/rdeps.Gravatar Nathan Harmata2017-03-08
| | | | | | -- PiperOrigin-RevId: 149431500 MOS_MIGRATED_REVID=149431500
* Global cleanup change.Gravatar Googler2017-03-03
| | | | | | -- PiperOrigin-RevId: 149089903 MOS_MIGRATED_REVID=149089903
* Rollback of commit 822c37816ac669e51bec3853b41849a19ec5e230.Gravatar Nathan Harmata2017-03-01
| | | | | | -- PiperOrigin-RevId: 148844518 MOS_MIGRATED_REVID=148844518
* Reimplement blaze query using an async evaluation model. Use a concurrent ↵Gravatar Nathan Harmata2017-02-28
| | | | | | | | | | | | | | | | | | | backend for SkyQueryEnvironment's implementation in order to achieve parallelism. Advantages: -New design has no flaws that the old design had. -Code is structured so that deadlocks due to thread starvation are impossible (yup!). Disadvantages: -The meat of this change needs to all be in a single CL because every single QueryFunction and QueryExpression needs to be rewritten in the async style. Still TODO: -Fully embrace the async model in all QueryFunctions (e.g. 'rdeps', 'allpaths'). -Use concurrency in BlazeQueryEnvironment to achieve parallel evaluation for (non SkyQuery) 'blaze query' and genquery. -- PiperOrigin-RevId: 148690279 MOS_MIGRATED_REVID=148690279
* Reword comment about the current implementation of ^.Gravatar Nathan Harmata2017-02-27
| | | | | | -- PiperOrigin-RevId: 148488719 MOS_MIGRATED_REVID=148488719
* Fix a hypothetical issue with 'buildfiles' and 'loadfiles' with duplicate ↵Gravatar Nathan Harmata2017-02-16
| | | | | | | | | | | | | | | | | | targets. These two functions don't use a Uniquifier internally so if the same bzl file foo.bzl is loaded multiple ways in 'e' in 'loadfiles(e)' then 'f' in 'f(loadfiles(e))' will observe foo.bzl multiple times. This isn't observable in practice (i.e. I cannot write a black-box query test that would fail without this CL) because: (1) BlazeQueryEnvironment#eval(QueryExpression, VariableContext<Target>, Callback<Target>) uses an intermediate aggregating callback and thus doesn't use the streaming query evaluation model. This means that the internal deduping in BlazeQueryEnvironment#getBuildFiles is sufficient. (2) SkyQueryEnvironment uses an outer BatchStreamedCallback which internally uses a Uniquifier. Still, this CL is useful for SkyQuery because without we're doing wasted work (e.g. in my example above, 'f' will wastefully do duplicate work with the .bzl files from the inner loadfiles(e)) because the deduping happens on the final query result, not on the intermediate result from 'buildfiles'/'loadfiles'. For 'buildfiles', there's an additional wart with (1) above because FakeSubincludeTarget doesn't override Object#equals/hashCode. -- PiperOrigin-RevId: 147656183 MOS_MIGRATED_REVID=147656183
* Give a more helpful error message on malformed regexes.Gravatar Nathan Harmata2017-02-16
| | | | | | -- PiperOrigin-RevId: 147621296 MOS_MIGRATED_REVID=147621296
* Global cleanup change.Gravatar Googler2017-01-25
| | | | | | -- PiperOrigin-RevId: 145473478 MOS_MIGRATED_REVID=145473478
* Remove dead code referencing deleted "suites" attribute.Gravatar Greg Estren2016-12-21
| | | | | | | | | This used to be how test_suites depended on other test_suites. Now they just go in "tests". -- PiperOrigin-RevId: 142607603 MOS_MIGRATED_REVID=142607603
* Rollback of commit e0a330577d9fe98169645cb68d9fc22cc787eeb6.Gravatar Janak Ramakrishnan2016-12-21
| | | | | | | | | | *** Reason for rollback *** Investigating if causes deadlock/thread starvation. -- PiperOrigin-RevId: 142575769 MOS_MIGRATED_REVID=142575769
* Some improvements to ParallelQueryUtils.Gravatar Nathan Harmata2016-12-16
| | | | | | | | | | | | | | | | | | | | | | | | (i) Use a CountDownLatch in ParallelQueryUtils#executeQueryTasksAndWaitInterruptibly to avoid busy-looping while waiting for query subtask completion (this busy-looping unnecessarily ties up a thread). But we still retain the fail-fast semantics we want (I renamed the method to emphasize this). (ii) Also have a special-case in ParallelQueryUtils#executeQueryTasksAndWaitInterruptibly for evaluating one query subtask so we don't wastefully use another thread. (iii) Also add ThreadSafety annotations to ParallelQueryUtils. ---- (i) and (ii) combine to address the following theoretical issue. Suppose we're evaluating a query expression of the form "(e1 - e2) + (e3 - e4)". The old code would (with the worst-case FJP thread scheduling) have the following threads at the _same_ time: Main QueryCommand thread - executeQueryTasksAndWaitInterruptibly(queryTasks = [(e1 - e2), (e3 - e4)] FJP thread - executeQueryTasksAndWaitInterruptibly(queryTasks = [e2]) FJP thread - eval(e2) FJP thread - executeQueryTasksAndWaitInterruptibly(queryTasks = [e4]) FJP thread - eval(e4) So of those 5 concurrent threads, 3 would be doing busy-loop waiting. For more pathological query expressions, we could end up tying up lots of threads doing wasteful busy-loops. -- PiperOrigin-RevId: 142215680 MOS_MIGRATED_REVID=142215680
* Make Argument factory methods public.Gravatar Nathan Harmata2016-12-13
| | | | | | -- PiperOrigin-RevId: 141920696 MOS_MIGRATED_REVID=141920696
* Rephrase query transformation in terms of composition of QueryExpressionMappers.Gravatar Nathan Harmata2016-12-13
| | | | | | -- PiperOrigin-RevId: 141904124 MOS_MIGRATED_REVID=141904124
* Fix bad bug with the parallel implementation of BinaryOperatorExpression. ↵Gravatar Nathan Harmata2016-12-12
| | | | | | | | | | | | | | Turns out that ForkJoinTask#adapt(Callable) returns a ForkJoinTask whose Future#get on error throws a ExecutionException wrapping a RuntimeException wrapping the thrown checked exception from the callable. This is documented behavior [1] that I incorrectly didn't know about. The additional level of wrapping meant that the catch-block of the parallel implementation of BinaryOperatorExpression wasn't rethrowing the InterruptedException/QueryException that the parallel task threw. The subtly in this bug is that the query expression being evaluated needs to be of the form "e1 + e2", where evaluation of "e1" throws a QueryException even in keepGoing mode (note that most of the query errors actually go through AbstractBlazeQueryEnvironment#reportBuildFileError). The test I wrote picks on LetExpression's evaluation-time (rather than e.g. parsing time) validation of the variable name. [1] https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinTask.html#adapt(java.util.concurrent.Callable) -- PiperOrigin-RevId: 141772584 MOS_MIGRATED_REVID=141772584
* Fix spelling mistake.Gravatar Nathan Harmata2016-12-06
| | | | | | -- PiperOrigin-RevId: 141178325 MOS_MIGRATED_REVID=141178325
* For all function expressions of the form f(..., e1, ..., e2, ..., eK, ...), ↵Gravatar Nathan Harmata2016-12-02
| | | | | | | | ensure that all of e1, e2, ..., and eK are elligble for parallel evaluation. This is _not_ the same as providing a parallel implementation of f, which we can do separately in followup CLs. -- PiperOrigin-RevId: 140861694 MOS_MIGRATED_REVID=140861694
* Provide a parallel implementation of "e1 - e2 - e3" by noting its ↵Gravatar Nathan Harmata2016-11-21
| | | | | | | equivalence to "e1 - (e2 + e3)" and the fact that we already have a parallel implementation of "e2 + e3". -- MOS_MIGRATED_REVID=139792288
* Enable parallel evaluation of 'e' in query expressions of the form ↵Gravatar Nathan Harmata2016-11-21
| | | | | | | 'buildfiles(e)'. -- MOS_MIGRATED_REVID=139787078
* Provide a parallel implementation of "e1 + e2".Gravatar Nathan Harmata2016-11-21
| | | | | -- MOS_MIGRATED_REVID=139613681
* Introduce a failFast mode to OutputFormatterCallback#close.Gravatar Nathan Harmata2016-11-18
| | | | | -- MOS_MIGRATED_REVID=139508838
* Make TargetPattern evaluation during query evaluation more parallel-friendly ↵Gravatar Nathan Harmata2016-11-15
| | | | | | | by introducing TargetPattern#parEval, which allows TargetPatterns' evaluations to explicitly have parallel implementations (no need to secretly use a FJP). -- MOS_MIGRATED_REVID=139101922
* Have query Lexer operated directly on StringGravatar Michajlo Matijkiw2016-11-02
| | | | | | | | No need for the char[] in the middle, prevents us from accidentally modifying input, or sucking up ram on huge queries. -- MOS_MIGRATED_REVID=137872573
* Unify AbstractBlazeQueryEnvironment#evaluateQuery with its subclass ↵Gravatar Nathan Harmata2016-10-04
| | | | | | | overrides. Also, have AbstractBlazeQueryEnvironment#evaluateQuery take an OutputFormatterCallback instance rather than a Callback instance. This is more sensible since the latter is only intended to be used intra-query, while the former is intended for usage in end-to-end query evaluation. This lets us slightly simplify QueryCommand, by shifting the responsibility for managing the OutputFormatterCallback to AbstractBlazeQueryEnvironment#evaluateQuery. -- MOS_MIGRATED_REVID=134827588
* Provide parallel implementations of 'allrdeps' and 'rbuildfiles', using a ↵Gravatar Nathan Harmata2016-09-29
| | | | | | | shared naive BFS implementation. Also implement RegexFilterExpression#parEval. -- MOS_MIGRATED_REVID=134598046
* Use ForkJoinPool, rather than ListeningExecutorService, for parallel query ↵Gravatar Nathan Harmata2016-09-22
| | | | | | | evaluation in SkyQueryEnvironment. FJP is nicer to program against, imo. -- MOS_MIGRATED_REVID=133844508
* Have SkyQueryEnvironment#getRBuildFiles not visit skyframe nodes more than ↵Gravatar Nathan Harmata2016-09-12
| | | | | | | once. This is helpful when there are multiple skylark reverse 'load' paths from the same popular .bzl file to a single BUILD file. As an implementation detail, introduce a few ThreadSafeUniquifier things (these will also be used in followup CLs). -- MOS_MIGRATED_REVID=132680777
* Boilerplate for parallel evaluation of FunctionExpression query expression ↵Gravatar Nathan Harmata2016-09-09
| | | | | | | nodes. -- MOS_MIGRATED_REVID=132558031
* A bunch of small changes to prepare SkyQueryEnvironment for full-parallel ↵Gravatar Nathan Harmata2016-09-08
| | | | | | | | | | | | | | evaluation: -Rename QueryExpression#evalConcurrently to QueryExpression#parEval. (parallelism is not concurrency! See https://existentialtype.wordpress.com/2011/03/17/parallelism-is-not-concurrency/) -Have SkyQueryEnvironment#eval (used recursively in #evaluateQuery) dynamically call QueryExpression#parEval when appropriate. -Delete QueryExpression#canEvalConcurrently. -Add ThreadSafety annotations in a bunch of relevant places in the query codebase. -A bunch of testing infrastructure to test parallel query evaluation. -TODOs for implementing parallel evaluation of all QueryExpression nodes. -- MOS_MIGRATED_REVID=132436340
* Allow Skyframe graph lookups and value retrievals to throw InterruptedException.Gravatar Janak Ramakrishnan2016-08-16
| | | | | | | The only place we now don't handle InterruptedException is in the action graph created after analysis, since I'm not sure that will be around for that much longer. -- MOS_MIGRATED_REVID=130327770
* Stream the right-hand side of subtractive query expressions. This means only ↵Gravatar Eric Fellheimer2016-08-12
| | | | | | | | | the left-hand side needs to be pinned fully into memory. Intersection is not associative, so we can't do the same thing there. For example, "abc" ^ "abc" = "abc", but "abc" ^ "a" ^ "b" ^ "c" = <null>. -- MOS_MIGRATED_REVID=130015098
* Fix embarassing typo in VariableContext#with.Gravatar Nathan Harmata2016-07-15
| | | | | | | | | Turns out that our existing test coverage was insufficient for catching this (I misread the tests during development of unknown commit and thus incorrectly thought we had test coverage for this). -- MOS_MIGRATED_REVID=127461716
* Re-implement variables in the blaze query language. Instead of using a ↵Gravatar Nathan Harmata2016-07-14
| | | | | | | | | mutable global context of variable bindings, pass around immutable local contexts. The motivation is so we can safely evaluate all blaze query expressions concurrently under the hood. A global context is hostile to this goal. -- MOS_MIGRATED_REVID=127324600
* No longer allow QueryExpressionMapper#map to throw a QueryException. This ↵Gravatar Nathan Harmata2016-07-04
| | | | | | | was unnecessary. -- MOS_MIGRATED_REVID=126457804
* (1) Allow QueryExpressionMapper#map to throw a QueryException.Gravatar Nathan Harmata2016-07-01
| | | | | | | | (2) Refactor the simple query concurrency support by introducing QueryExpression#canEvalConcurrently and removing the primitive BinaryOperatorExpression#evalConcurrently and the hardcoded SkyQueryEnvironment logic around it. This way each QueryExpression can safely manage its own concurrency. A followup CL will ensure that concurrent evaluation occurs for as much of the query expression as possible, rather than just for the top-level query expression node. (3) Make a few query internals public. -- MOS_MIGRATED_REVID=126324637
* Add SkyQuery-specific allrdeps implementation to allow batch getReverseDepsGravatar Googler2016-06-27
| | | | | | | with maximum limit -- MOS_MIGRATED_REVID=125959807
* Parallelize (some of) BinaryOperatorExpressionGravatar Mark Schaller2016-06-22
| | | | | | | | | | | | | | | | | | | | | | | | Adds evalConcurrently to QueryExpression so that expression implementations that support concurrent evaluation can do so using the supplied executor service. Implements concurrent evaluation for the PLUS/UNION cases of BinaryOperatorExpression. Because evalConcurrently requires its callback to be threadsafe, but the callback passed to evaluateQuery may only be called by one thread at a time, this change makes the BatchStreamedCallback constructed by SkyQueryEnvironment threadsafe, including its uniquifier. However, there is a thread-safety problem when the operands of BinaryOperatorExpression are LetExpressions, because their evaluation involves mutating state in the query environment. A future change will fix that. For now, concurrent evaluation is only attempted when the query expression is a BinaryOperatorExpression and all its operands are target literals. -- MOS_MIGRATED_REVID=125505247
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-07 15:08:58 +0000