rustc_query_system/query/
job.rs1use std::fmt::Debug;
2use std::hash::Hash;
3use std::io::Write;
4use std::iter;
5use std::num::NonZero;
6use std::sync::Arc;
7
8use parking_lot::{Condvar, Mutex};
9use rustc_data_structures::fx::{FxHashMap, FxHashSet};
10use rustc_data_structures::jobserver;
11use rustc_errors::{Diag, DiagCtxtHandle};
12use rustc_hir::def::DefKind;
13use rustc_session::Session;
14use rustc_span::{DUMMY_SP, Span};
15
16use super::QueryStackFrameExtra;
17use crate::dep_graph::DepContext;
18use crate::error::CycleStack;
19use crate::query::plumbing::CycleError;
20use crate::query::{QueryContext, QueryStackFrame};
21
22#[derive(Clone, Debug)]
24pub struct QueryInfo<I> {
25 pub span: Span,
27 pub query: QueryStackFrame<I>,
28}
29
30impl<I> QueryInfo<I> {
31 pub(crate) fn lift<Qcx: QueryContext<QueryInfo = I>>(
32 &self,
33 qcx: Qcx,
34 ) -> QueryInfo<QueryStackFrameExtra> {
35 QueryInfo { span: self.span, query: self.query.lift(qcx) }
36 }
37}
38
39pub type QueryMap<I> = FxHashMap<QueryJobId, QueryJobInfo<I>>;
40
41#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
43pub struct QueryJobId(pub NonZero<u64>);
44
45impl QueryJobId {
46 fn query<I: Clone>(self, map: &QueryMap<I>) -> QueryStackFrame<I> {
47 map.get(&self).unwrap().query.clone()
48 }
49
50 fn span<I>(self, map: &QueryMap<I>) -> Span {
51 map.get(&self).unwrap().job.span
52 }
53
54 fn parent<I>(self, map: &QueryMap<I>) -> Option<QueryJobId> {
55 map.get(&self).unwrap().job.parent
56 }
57
58 fn latch<I>(self, map: &QueryMap<I>) -> Option<&QueryLatch<I>> {
59 map.get(&self).unwrap().job.latch.as_ref()
60 }
61}
62
63#[derive(Clone, Debug)]
64pub struct QueryJobInfo<I> {
65 pub query: QueryStackFrame<I>,
66 pub job: QueryJob<I>,
67}
68
69#[derive(Debug)]
71pub struct QueryJob<I> {
72 pub id: QueryJobId,
73
74 pub span: Span,
76
77 pub parent: Option<QueryJobId>,
79
80 latch: Option<QueryLatch<I>>,
82}
83
84impl<I> Clone for QueryJob<I> {
85 fn clone(&self) -> Self {
86 Self { id: self.id, span: self.span, parent: self.parent, latch: self.latch.clone() }
87 }
88}
89
90impl<I> QueryJob<I> {
91 #[inline]
93 pub fn new(id: QueryJobId, span: Span, parent: Option<QueryJobId>) -> Self {
94 QueryJob { id, span, parent, latch: None }
95 }
96
97 pub(super) fn latch(&mut self) -> QueryLatch<I> {
98 if self.latch.is_none() {
99 self.latch = Some(QueryLatch::new());
100 }
101 self.latch.as_ref().unwrap().clone()
102 }
103
104 #[inline]
109 pub fn signal_complete(self) {
110 if let Some(latch) = self.latch {
111 latch.set();
112 }
113 }
114}
115
116impl QueryJobId {
117 pub(super) fn find_cycle_in_stack<I: Clone>(
118 &self,
119 query_map: QueryMap<I>,
120 current_job: &Option<QueryJobId>,
121 span: Span,
122 ) -> CycleError<I> {
123 let mut cycle = Vec::new();
125 let mut current_job = Option::clone(current_job);
126
127 while let Some(job) = current_job {
128 let info = query_map.get(&job).unwrap();
129 cycle.push(QueryInfo { span: info.job.span, query: info.query.clone() });
130
131 if job == *self {
132 cycle.reverse();
133
134 cycle[0].span = span;
139 let usage = info
141 .job
142 .parent
143 .as_ref()
144 .map(|parent| (info.job.span, parent.query(&query_map)));
145 return CycleError { usage, cycle };
146 }
147
148 current_job = info.job.parent;
149 }
150
151 panic!("did not find a cycle")
152 }
153
154 #[cold]
155 #[inline(never)]
156 pub fn find_dep_kind_root<I: Clone>(&self, query_map: QueryMap<I>) -> (QueryJobInfo<I>, usize) {
157 let mut depth = 1;
158 let info = query_map.get(&self).unwrap();
159 let dep_kind = info.query.dep_kind;
160 let mut current_id = info.job.parent;
161 let mut last_layout = (info.clone(), depth);
162
163 while let Some(id) = current_id {
164 let info = query_map.get(&id).unwrap();
165 if info.query.dep_kind == dep_kind {
166 depth += 1;
167 last_layout = (info.clone(), depth);
168 }
169 current_id = info.job.parent;
170 }
171 last_layout
172 }
173}
174
175#[derive(Debug)]
176struct QueryWaiter<I> {
177 query: Option<QueryJobId>,
178 condvar: Condvar,
179 span: Span,
180 cycle: Mutex<Option<CycleError<I>>>,
181}
182
183#[derive(Debug)]
184struct QueryLatchInfo<I> {
185 complete: bool,
186 waiters: Vec<Arc<QueryWaiter<I>>>,
187}
188
189#[derive(Debug)]
190pub(super) struct QueryLatch<I> {
191 info: Arc<Mutex<QueryLatchInfo<I>>>,
192}
193
194impl<I> Clone for QueryLatch<I> {
195 fn clone(&self) -> Self {
196 Self { info: Arc::clone(&self.info) }
197 }
198}
199
200impl<I> QueryLatch<I> {
201 fn new() -> Self {
202 QueryLatch {
203 info: Arc::new(Mutex::new(QueryLatchInfo { complete: false, waiters: Vec::new() })),
204 }
205 }
206
207 pub(super) fn wait_on(
209 &self,
210 query: Option<QueryJobId>,
211 span: Span,
212 ) -> Result<(), CycleError<I>> {
213 let waiter =
214 Arc::new(QueryWaiter { query, span, cycle: Mutex::new(None), condvar: Condvar::new() });
215 self.wait_on_inner(&waiter);
216 let mut cycle = waiter.cycle.lock();
220 match cycle.take() {
221 None => Ok(()),
222 Some(cycle) => Err(cycle),
223 }
224 }
225
226 fn wait_on_inner(&self, waiter: &Arc<QueryWaiter<I>>) {
228 let mut info = self.info.lock();
229 if !info.complete {
230 info.waiters.push(Arc::clone(waiter));
235
236 rayon_core::mark_blocked();
240 jobserver::release_thread();
241 waiter.condvar.wait(&mut info);
242 drop(info);
244 jobserver::acquire_thread();
245 }
246 }
247
248 fn set(&self) {
250 let mut info = self.info.lock();
251 debug_assert!(!info.complete);
252 info.complete = true;
253 let registry = rayon_core::Registry::current();
254 for waiter in info.waiters.drain(..) {
255 rayon_core::mark_unblocked(®istry);
256 waiter.condvar.notify_one();
257 }
258 }
259
260 fn extract_waiter(&self, waiter: usize) -> Arc<QueryWaiter<I>> {
263 let mut info = self.info.lock();
264 debug_assert!(!info.complete);
265 info.waiters.remove(waiter)
267 }
268}
269
270type Waiter = (QueryJobId, usize);
272
273fn visit_waiters<I, F>(
283 query_map: &QueryMap<I>,
284 query: QueryJobId,
285 mut visit: F,
286) -> Option<Option<Waiter>>
287where
288 F: FnMut(Span, QueryJobId) -> Option<Option<Waiter>>,
289{
290 if let Some(parent) = query.parent(query_map) {
292 if let Some(cycle) = visit(query.span(query_map), parent) {
293 return Some(cycle);
294 }
295 }
296
297 if let Some(latch) = query.latch(query_map) {
299 for (i, waiter) in latch.info.lock().waiters.iter().enumerate() {
300 if let Some(waiter_query) = waiter.query {
301 if visit(waiter.span, waiter_query).is_some() {
302 return Some(Some((query, i)));
304 }
305 }
306 }
307 }
308
309 None
310}
311
312fn cycle_check<I>(
317 query_map: &QueryMap<I>,
318 query: QueryJobId,
319 span: Span,
320 stack: &mut Vec<(Span, QueryJobId)>,
321 visited: &mut FxHashSet<QueryJobId>,
322) -> Option<Option<Waiter>> {
323 if !visited.insert(query) {
324 return if let Some(p) = stack.iter().position(|q| q.1 == query) {
325 stack.drain(0..p);
329 stack[0].0 = span;
331 Some(None)
332 } else {
333 None
334 };
335 }
336
337 stack.push((span, query));
339
340 let r = visit_waiters(query_map, query, |span, successor| {
342 cycle_check(query_map, successor, span, stack, visited)
343 });
344
345 if r.is_none() {
347 stack.pop();
348 }
349
350 r
351}
352
353fn connected_to_root<I>(
357 query_map: &QueryMap<I>,
358 query: QueryJobId,
359 visited: &mut FxHashSet<QueryJobId>,
360) -> bool {
361 if !visited.insert(query) {
363 return false;
364 }
365
366 if query.parent(query_map).is_none() {
368 return true;
369 }
370
371 visit_waiters(query_map, query, |_, successor| {
372 connected_to_root(query_map, successor, visited).then_some(None)
373 })
374 .is_some()
375}
376
377fn pick_query<'a, I: Clone, T, F>(query_map: &QueryMap<I>, queries: &'a [T], f: F) -> &'a T
379where
380 F: Fn(&T) -> (Span, QueryJobId),
381{
382 queries
385 .iter()
386 .min_by_key(|v| {
387 let (span, query) = f(v);
388 let hash = query.query(query_map).hash;
389 let span_cmp = if span == DUMMY_SP { 1 } else { 0 };
393 (span_cmp, hash)
394 })
395 .unwrap()
396}
397
398fn remove_cycle<I: Clone>(
404 query_map: &QueryMap<I>,
405 jobs: &mut Vec<QueryJobId>,
406 wakelist: &mut Vec<Arc<QueryWaiter<I>>>,
407) -> bool {
408 let mut visited = FxHashSet::default();
409 let mut stack = Vec::new();
410 if let Some(waiter) =
412 cycle_check(query_map, jobs.pop().unwrap(), DUMMY_SP, &mut stack, &mut visited)
413 {
414 let (mut spans, queries): (Vec<_>, Vec<_>) = stack.into_iter().rev().unzip();
417
418 spans.rotate_right(1);
420
421 let mut stack: Vec<_> = iter::zip(spans, queries).collect();
423
424 for r in &stack {
426 if let Some(pos) = jobs.iter().position(|j| j == &r.1) {
427 jobs.remove(pos);
428 }
429 }
430
431 let entry_points = stack
434 .iter()
435 .filter_map(|&(span, query)| {
436 if query.parent(query_map).is_none() {
437 Some((span, query, None))
439 } else {
440 let mut waiters = Vec::new();
441 visit_waiters(query_map, query, |span, waiter| {
443 let mut visited = FxHashSet::from_iter(stack.iter().map(|q| q.1));
445
446 if connected_to_root(query_map, waiter, &mut visited) {
447 waiters.push((span, waiter));
448 }
449
450 None
451 });
452 if waiters.is_empty() {
453 None
454 } else {
455 let waiter = *pick_query(query_map, &waiters, |s| *s);
457 Some((span, query, Some(waiter)))
458 }
459 }
460 })
461 .collect::<Vec<(Span, QueryJobId, Option<(Span, QueryJobId)>)>>();
462
463 let (_, entry_point, usage) = pick_query(query_map, &entry_points, |e| (e.0, e.1));
465
466 let entry_point_pos = stack.iter().position(|(_, query)| query == entry_point);
468 if let Some(pos) = entry_point_pos {
469 stack.rotate_left(pos);
470 }
471
472 let usage = usage.as_ref().map(|(span, query)| (*span, query.query(query_map)));
473
474 let error = CycleError {
476 usage,
477 cycle: stack
478 .iter()
479 .map(|&(s, ref q)| QueryInfo { span: s, query: q.query(query_map) })
480 .collect(),
481 };
482
483 let (waitee_query, waiter_idx) = waiter.unwrap();
486
487 let waiter = waitee_query.latch(query_map).unwrap().extract_waiter(waiter_idx);
489
490 *waiter.cycle.lock() = Some(error);
492
493 wakelist.push(waiter);
495
496 true
497 } else {
498 false
499 }
500}
501
502pub fn break_query_cycles<I: Clone + Debug>(
508 query_map: QueryMap<I>,
509 registry: &rayon_core::Registry,
510) {
511 let mut wakelist = Vec::new();
512 let mut jobs: Vec<QueryJobId> = query_map.keys().cloned().collect();
513
514 let mut found_cycle = false;
515
516 while jobs.len() > 0 {
517 if remove_cycle(&query_map, &mut jobs, &mut wakelist) {
518 found_cycle = true;
519 }
520 }
521
522 if !found_cycle {
530 panic!(
531 "deadlock detected as we're unable to find a query cycle to break\n\
532 current query map:\n{:#?}",
533 query_map
534 );
535 }
536
537 for _ in 0..wakelist.len() {
541 rayon_core::mark_unblocked(registry);
542 }
543
544 for waiter in wakelist.into_iter() {
545 waiter.condvar.notify_one();
546 }
547}
548
549#[inline(never)]
550#[cold]
551pub fn report_cycle<'a>(
552 sess: &'a Session,
553 CycleError { usage, cycle: stack }: &CycleError,
554) -> Diag<'a> {
555 assert!(!stack.is_empty());
556
557 let span = stack[0].query.info.default_span(stack[1 % stack.len()].span);
558
559 let mut cycle_stack = Vec::new();
560
561 use crate::error::StackCount;
562 let stack_count = if stack.len() == 1 { StackCount::Single } else { StackCount::Multiple };
563
564 for i in 1..stack.len() {
565 let query = &stack[i].query;
566 let span = query.info.default_span(stack[(i + 1) % stack.len()].span);
567 cycle_stack.push(CycleStack { span, desc: query.info.description.to_owned() });
568 }
569
570 let mut cycle_usage = None;
571 if let Some((span, ref query)) = *usage {
572 cycle_usage = Some(crate::error::CycleUsage {
573 span: query.info.default_span(span),
574 usage: query.info.description.to_string(),
575 });
576 }
577
578 let alias =
579 if stack.iter().all(|entry| matches!(entry.query.info.def_kind, Some(DefKind::TyAlias))) {
580 Some(crate::error::Alias::Ty)
581 } else if stack.iter().all(|entry| entry.query.info.def_kind == Some(DefKind::TraitAlias)) {
582 Some(crate::error::Alias::Trait)
583 } else {
584 None
585 };
586
587 let cycle_diag = crate::error::Cycle {
588 span,
589 cycle_stack,
590 stack_bottom: stack[0].query.info.description.to_owned(),
591 alias,
592 cycle_usage,
593 stack_count,
594 note_span: (),
595 };
596
597 sess.dcx().create_err(cycle_diag)
598}
599
600pub fn print_query_stack<Qcx: QueryContext>(
601 qcx: Qcx,
602 mut current_query: Option<QueryJobId>,
603 dcx: DiagCtxtHandle<'_>,
604 limit_frames: Option<usize>,
605 mut file: Option<std::fs::File>,
606) -> usize {
607 let mut count_printed = 0;
611 let mut count_total = 0;
612
613 let query_map = match qcx.collect_active_jobs() {
615 Ok(query_map) => query_map,
616 Err(query_map) => query_map,
617 };
618
619 if let Some(ref mut file) = file {
620 let _ = writeln!(file, "\n\nquery stack during panic:");
621 }
622 while let Some(query) = current_query {
623 let Some(query_info) = query_map.get(&query) else {
624 break;
625 };
626 let query_extra = qcx.lift_query_info(&query_info.query.info);
627 if Some(count_printed) < limit_frames || limit_frames.is_none() {
628 #[allow(rustc::diagnostic_outside_of_impl)]
631 #[allow(rustc::untranslatable_diagnostic)]
632 dcx.struct_failure_note(format!(
633 "#{} [{:?}] {}",
634 count_printed, query_info.query.dep_kind, query_extra.description
635 ))
636 .with_span(query_info.job.span)
637 .emit();
638 count_printed += 1;
639 }
640
641 if let Some(ref mut file) = file {
642 let _ = writeln!(
643 file,
644 "#{} [{}] {}",
645 count_total,
646 qcx.dep_context().dep_kind_info(query_info.query.dep_kind).name,
647 query_extra.description
648 );
649 }
650
651 current_query = query_info.job.parent;
652 count_total += 1;
653 }
654
655 if let Some(ref mut file) = file {
656 let _ = writeln!(file, "end of query stack");
657 }
658 count_total
659}