diff options
| author | bors <bors@rust-lang.org> | 2024-08-31 08:48:35 +0000 |
|---|---|---|
| committer | bors <bors@rust-lang.org> | 2024-08-31 08:48:35 +0000 |
| commit | 9649706eada1b2c68cf6504356efb058f68ad739 (patch) | |
| tree | 56962b1c7e8f6064ad1b13548feb2ec07b0e30be | |
| parent | fa72f0763de6bc1596208fc1419883ce5aea0de4 (diff) | |
| parent | 25e3b6641018a917c7e7bcbd1dfc593f15eeb6e3 (diff) | |
| download | rust-9649706eada1b2c68cf6504356efb058f68ad739.tar.gz rust-9649706eada1b2c68cf6504356efb058f68ad739.zip | |
Auto merge of #129809 - matthiaskrgr:rollup-cyygnxh, r=matthiaskrgr
Rollup of 15 pull requests Successful merges: - #120221 (Don't make statement nonterminals match pattern nonterminals) - #126183 (Separate core search logic with search ui) - #129123 (rustdoc-json: Add test for `Self` type) - #129366 (linker: Synchronize native library search in rustc and linker) - #129527 (Don't use `TyKind` in a lint) - #129534 (Deny `wasm_c_abi` lint to nudge the last 25%) - #129640 (Re-enable android tests/benches in alloc/core) - #129642 (Bump backtrace to 0.3.74~ish) - #129675 (allow BufReader::peek to be called on unsized types) - #129723 (Simplify some extern providers) - #129724 (Remove `Option<!>` return types.) - #129725 (Stop using `ty::GenericPredicates` for non-predicates_of queries) - #129731 (Allow running `./x.py test compiler`) - #129751 (interpret/visitor: make memory order iteration slightly more efficient) - #129754 (wasi: Fix sleeping for `Duration::MAX`) r? `@ghost` `@rustbot` modify labels: rollup
55 files changed, 2833 insertions, 2693 deletions
diff --git a/compiler/rustc_ast/src/token.rs b/compiler/rustc_ast/src/token.rs index 43d87b96ead..f1dddb3acac 100644 --- a/compiler/rustc_ast/src/token.rs +++ b/compiler/rustc_ast/src/token.rs @@ -486,6 +486,9 @@ impl Token { } /// Returns `true` if the token can appear at the start of an expression. + /// + /// **NB**: Take care when modifying this function, since it will change + /// the stable set of tokens that are allowed to match an expr nonterminal. pub fn can_begin_expr(&self) -> bool { match self.uninterpolate().kind { Ident(name, is_raw) => @@ -504,10 +507,13 @@ impl Token { PathSep | // global path Lifetime(..) | // labeled loop Pound => true, // expression attributes - Interpolated(ref nt) => matches!(&**nt, NtLiteral(..) | - NtExpr(..) | - NtBlock(..) | - NtPath(..)), + Interpolated(ref nt) => + matches!(&**nt, + NtBlock(..) | + NtExpr(..) | + NtLiteral(..) | + NtPath(..) + ), _ => false, } } @@ -515,23 +521,32 @@ impl Token { /// Returns `true` if the token can appear at the start of a pattern. /// /// Shamelessly borrowed from `can_begin_expr`, only used for diagnostics right now. - pub fn can_begin_pattern(&self) -> bool { - match self.uninterpolate().kind { - Ident(name, is_raw) => - ident_can_begin_expr(name, self.span, is_raw), // value name or keyword - | OpenDelim(Delimiter::Bracket | Delimiter::Parenthesis) // tuple or array - | Literal(..) // literal - | BinOp(Minus) // unary minus - | BinOp(And) // reference - | AndAnd // double reference - // DotDotDot is no longer supported - | DotDot | DotDotDot | DotDotEq // ranges - | Lt | BinOp(Shl) // associated path - | PathSep => true, // global path - Interpolated(ref nt) => matches!(&**nt, NtLiteral(..) | - NtPat(..) | - NtBlock(..) | - NtPath(..)), + pub fn can_begin_pattern(&self, pat_kind: NtPatKind) -> bool { + match &self.uninterpolate().kind { + // box, ref, mut, and other identifiers (can stricten) + Ident(..) | NtIdent(..) | + OpenDelim(Delimiter::Parenthesis) | // tuple pattern + OpenDelim(Delimiter::Bracket) | // slice pattern + BinOp(And) | // reference + BinOp(Minus) | // negative literal + AndAnd | // double reference + Literal(_) | // literal + DotDot | // range pattern (future compat) + DotDotDot | // range pattern (future compat) + PathSep | // path + Lt | // path (UFCS constant) + BinOp(Shl) => true, // path (double UFCS) + // leading vert `|` or-pattern + BinOp(Or) => matches!(pat_kind, PatWithOr), + Interpolated(nt) => + matches!(&**nt, + | NtExpr(..) + | NtLiteral(..) + | NtMeta(..) + | NtPat(..) + | NtPath(..) + | NtTy(..) + ), _ => false, } } diff --git a/compiler/rustc_codegen_ssa/src/back/link.rs b/compiler/rustc_codegen_ssa/src/back/link.rs index 4d19425255f..e8143b9a5f3 100644 --- a/compiler/rustc_codegen_ssa/src/back/link.rs +++ b/compiler/rustc_codegen_ssa/src/back/link.rs @@ -2,7 +2,7 @@ use std::collections::BTreeSet; use std::ffi::OsString; use std::fs::{read, File, OpenOptions}; use std::io::{BufWriter, Write}; -use std::ops::Deref; +use std::ops::{ControlFlow, Deref}; use std::path::{Path, PathBuf}; use std::process::{ExitStatus, Output, Stdio}; use std::{env, fmt, fs, io, mem, str}; @@ -18,8 +18,8 @@ use rustc_data_structures::temp_dir::MaybeTempDir; use rustc_errors::{DiagCtxtHandle, ErrorGuaranteed, FatalError}; use rustc_fs_util::{fix_windows_verbatim_for_gcc, try_canonicalize}; use rustc_hir::def_id::{CrateNum, LOCAL_CRATE}; -use rustc_metadata::find_native_static_library; use rustc_metadata::fs::{copy_to_stdout, emit_wrapper_file, METADATA_FILENAME}; +use rustc_metadata::{find_native_static_library, walk_native_lib_search_dirs}; use rustc_middle::bug; use rustc_middle::middle::debugger_visualizer::DebuggerVisualizerFile; use rustc_middle::middle::dependency_format::Linkage; @@ -2110,50 +2110,19 @@ fn add_library_search_dirs( return; } - // Library search paths explicitly supplied by user (`-L` on the command line). - for search_path in sess.target_filesearch(PathKind::Native).cli_search_paths() { - cmd.include_path(&fix_windows_verbatim_for_gcc(&search_path.dir)); - } - for search_path in sess.target_filesearch(PathKind::Framework).cli_search_paths() { - // Contrary to the `-L` docs only framework-specific paths are considered here. - if search_path.kind != PathKind::All { - cmd.framework_path(&search_path.dir); - } - } - - // The toolchain ships some native library components and self-contained linking was enabled. - // Add the self-contained library directory to search paths. - if self_contained_components.intersects( - LinkSelfContainedComponents::LIBC - | LinkSelfContainedComponents::UNWIND - | LinkSelfContainedComponents::MINGW, - ) { - let lib_path = sess.target_tlib_path.dir.join("self-contained"); - cmd.include_path(&fix_windows_verbatim_for_gcc(&lib_path)); - } - - // Toolchains for some targets may ship `libunwind.a`, but place it into the main sysroot - // library directory instead of the self-contained directories. - // Sanitizer libraries have the same issue and are also linked by name on Apple targets. - // The targets here should be in sync with `copy_third_party_objects` in bootstrap. - // FIXME: implement `-Clink-self-contained=+/-unwind,+/-sanitizers`, move the shipped libunwind - // and sanitizers to self-contained directory, and stop adding this search path. - if sess.target.vendor == "fortanix" - || sess.target.os == "linux" - || sess.target.os == "fuchsia" - || sess.target.is_like_osx && !sess.opts.unstable_opts.sanitizer.is_empty() - { - cmd.include_path(&fix_windows_verbatim_for_gcc(&sess.target_tlib_path.dir)); - } - - // Mac Catalyst uses the macOS SDK, but to link to iOS-specific frameworks - // we must have the support library stubs in the library search path (#121430). - if let Some(sdk_root) = apple_sdk_root - && sess.target.llvm_target.contains("macabi") - { - cmd.include_path(&sdk_root.join("System/iOSSupport/usr/lib")); - cmd.framework_path(&sdk_root.join("System/iOSSupport/System/Library/Frameworks")); - } + walk_native_lib_search_dirs( + sess, + self_contained_components, + apple_sdk_root, + |dir, is_framework| { + if is_framework { + cmd.framework_path(dir); + } else { + cmd.include_path(&fix_windows_verbatim_for_gcc(dir)); + } + ControlFlow::<()>::Continue(()) + }, + ); } /// Add options making relocation sections in the produced ELF files read-only diff --git a/compiler/rustc_codegen_ssa/src/back/linker.rs b/compiler/rustc_codegen_ssa/src/back/linker.rs index fbab988a32b..cb266247e0d 100644 --- a/compiler/rustc_codegen_ssa/src/back/linker.rs +++ b/compiler/rustc_codegen_ssa/src/back/linker.rs @@ -7,7 +7,7 @@ use std::{env, iter, mem, str}; use cc::windows_registry; use rustc_hir::def_id::{CrateNum, LOCAL_CRATE}; -use rustc_metadata::find_native_static_library; +use rustc_metadata::{find_native_static_library, try_find_native_static_library}; use rustc_middle::bug; use rustc_middle::middle::dependency_format::Linkage; use rustc_middle::middle::exported_symbols; @@ -891,9 +891,15 @@ impl<'a> Linker for MsvcLinker<'a> { } fn link_staticlib_by_name(&mut self, name: &str, verbatim: bool, whole_archive: bool) { - let prefix = if whole_archive { "/WHOLEARCHIVE:" } else { "" }; - let suffix = if verbatim { "" } else { ".lib" }; - self.link_arg(format!("{prefix}{name}{suffix}")); + // On MSVC-like targets rustc supports static libraries using alternative naming + // scheme (`libfoo.a`) unsupported by linker, search for such libraries manually. + if let Some(path) = try_find_native_static_library(self.sess, name, verbatim) { + self.link_staticlib_by_path(&path, whole_archive); + } else { + let prefix = if whole_archive { "/WHOLEARCHIVE:" } else { "" }; + let suffix = if verbatim { "" } else { ".lib" }; + self.link_arg(format!("{prefix}{name}{suffix}")); + } } fn link_staticlib_by_path(&mut self, path: &Path, whole_archive: bool) { diff --git a/compiler/rustc_const_eval/src/interpret/visitor.rs b/compiler/rustc_const_eval/src/interpret/visitor.rs index fd649d608c6..b02f12e3c7f 100644 --- a/compiler/rustc_const_eval/src/interpret/visitor.rs +++ b/compiler/rustc_const_eval/src/interpret/visitor.rs @@ -25,14 +25,15 @@ pub trait ValueVisitor<'tcx, M: Machine<'tcx>>: Sized { } /// This function provides the chance to reorder the order in which fields are visited for - /// `FieldsShape::Aggregate`: The order of fields will be - /// `(0..num_fields).map(aggregate_field_order)`. + /// `FieldsShape::Aggregate`. /// - /// The default means we iterate in source declaration order; alternative this can do an inverse - /// lookup in `memory_index` to use memory field order instead. + /// The default means we iterate in source declaration order; alternatively this can do some + /// work with `memory_index` to iterate in memory order. #[inline(always)] - fn aggregate_field_order(_memory_index: &IndexVec<FieldIdx, u32>, idx: usize) -> usize { - idx + fn aggregate_field_iter( + memory_index: &IndexVec<FieldIdx, u32>, + ) -> impl Iterator<Item = FieldIdx> + 'static { + memory_index.indices() } // Recursive actions, ready to be overloaded. @@ -172,9 +173,9 @@ pub trait ValueVisitor<'tcx, M: Machine<'tcx>>: Sized { &FieldsShape::Union(fields) => { self.visit_union(v, fields)?; } - FieldsShape::Arbitrary { offsets, memory_index } => { - for idx in 0..offsets.len() { - let idx = Self::aggregate_field_order(memory_index, idx); + FieldsShape::Arbitrary { memory_index, .. } => { + for idx in Self::aggregate_field_iter(memory_index) { + let idx = idx.as_usize(); let field = self.ecx().project_field(v, idx)?; self.visit_field(v, idx, &field)?; } diff --git a/compiler/rustc_hir_analysis/src/collect.rs b/compiler/rustc_hir_analysis/src/collect.rs index 3acf2c63145..b8fbe0e99ef 100644 --- a/compiler/rustc_hir_analysis/src/collect.rs +++ b/compiler/rustc_hir_analysis/src/collect.rs @@ -420,7 +420,7 @@ impl<'tcx> HirTyLowerer<'tcx> for ItemCtxt<'tcx> { span: Span, def_id: LocalDefId, assoc_name: Ident, - ) -> ty::GenericPredicates<'tcx> { + ) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { self.tcx.at(span).type_param_predicates((self.item_def_id, def_id, assoc_name)) } diff --git a/compiler/rustc_hir_analysis/src/collect/predicates_of.rs b/compiler/rustc_hir_analysis/src/collect/predicates_of.rs index bba8b0497be..1bff91b1fac 100644 --- a/compiler/rustc_hir_analysis/src/collect/predicates_of.rs +++ b/compiler/rustc_hir_analysis/src/collect/predicates_of.rs @@ -580,24 +580,24 @@ pub(super) fn explicit_predicates_of<'tcx>( /// Ensures that the super-predicates of the trait with a `DefId` /// of `trait_def_id` are lowered and stored. This also ensures that /// the transitive super-predicates are lowered. -pub(super) fn explicit_super_predicates_of( - tcx: TyCtxt<'_>, +pub(super) fn explicit_super_predicates_of<'tcx>( + tcx: TyCtxt<'tcx>, trait_def_id: LocalDefId, -) -> ty::GenericPredicates<'_> { +) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { implied_predicates_with_filter(tcx, trait_def_id.to_def_id(), PredicateFilter::SelfOnly) } -pub(super) fn explicit_supertraits_containing_assoc_item( - tcx: TyCtxt<'_>, +pub(super) fn explicit_supertraits_containing_assoc_item<'tcx>( + tcx: TyCtxt<'tcx>, (trait_def_id, assoc_name): (DefId, Ident), -) -> ty::GenericPredicates<'_> { +) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { implied_predicates_with_filter(tcx, trait_def_id, PredicateFilter::SelfThatDefines(assoc_name)) } -pub(super) fn explicit_implied_predicates_of( - tcx: TyCtxt<'_>, +pub(super) fn explicit_implied_predicates_of<'tcx>( + tcx: TyCtxt<'tcx>, trait_def_id: LocalDefId, -) -> ty::GenericPredicates<'_> { +) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { implied_predicates_with_filter( tcx, trait_def_id.to_def_id(), @@ -612,11 +612,11 @@ pub(super) fn explicit_implied_predicates_of( /// Ensures that the super-predicates of the trait with a `DefId` /// of `trait_def_id` are lowered and stored. This also ensures that /// the transitive super-predicates are lowered. -pub(super) fn implied_predicates_with_filter( - tcx: TyCtxt<'_>, +pub(super) fn implied_predicates_with_filter<'tcx>( + tcx: TyCtxt<'tcx>, trait_def_id: DefId, filter: PredicateFilter, -) -> ty::GenericPredicates<'_> { +) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { let Some(trait_def_id) = trait_def_id.as_local() else { // if `assoc_name` is None, then the query should've been redirected to an // external provider @@ -679,20 +679,16 @@ pub(super) fn implied_predicates_with_filter( _ => {} } - ty::GenericPredicates { - parent: None, - predicates: implied_bounds, - effects_min_tys: ty::List::empty(), - } + ty::EarlyBinder::bind(implied_bounds) } /// Returns the predicates defined on `item_def_id` of the form /// `X: Foo` where `X` is the type parameter `def_id`. #[instrument(level = "trace", skip(tcx))] -pub(super) fn type_param_predicates( - tcx: TyCtxt<'_>, +pub(super) fn type_param_predicates<'tcx>( + tcx: TyCtxt<'tcx>, (item_def_id, def_id, assoc_name): (LocalDefId, LocalDefId, Ident), -) -> ty::GenericPredicates<'_> { +) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { use rustc_hir::*; use rustc_middle::ty::Ty; @@ -713,18 +709,20 @@ pub(super) fn type_param_predicates( tcx.generics_of(item_def_id).parent.map(|def_id| def_id.expect_local()) }; - let mut result = parent - .map(|parent| { - let icx = ItemCtxt::new(tcx, parent); - icx.probe_ty_param_bounds(DUMMY_SP, def_id, assoc_name) - }) - .unwrap_or_default(); + let result = if let Some(parent) = parent { + let icx = ItemCtxt::new(tcx, parent); + icx.probe_ty_param_bounds(DUMMY_SP, def_id, assoc_name) + } else { + ty::EarlyBinder::bind(&[] as &[_]) + }; let mut extend = None; let item_hir_id = tcx.local_def_id_to_hir_id(item_def_id); let hir_node = tcx.hir_node(item_hir_id); - let Some(hir_generics) = hir_node.generics() else { return result }; + let Some(hir_generics) = hir_node.generics() else { + return result; + }; if let Node::Item(item) = hir_node && let ItemKind::Trait(..) = item.kind // Implied `Self: Trait` and supertrait bounds. @@ -748,9 +746,10 @@ pub(super) fn type_param_predicates( _ => false, }), ); - result.predicates = - tcx.arena.alloc_from_iter(result.predicates.iter().copied().chain(extra_predicates)); - result + + ty::EarlyBinder::bind( + tcx.arena.alloc_from_iter(result.skip_binder().iter().copied().chain(extra_predicates)), + ) } impl<'tcx> ItemCtxt<'tcx> { diff --git a/compiler/rustc_hir_analysis/src/collect/resolve_bound_vars.rs b/compiler/rustc_hir_analysis/src/collect/resolve_bound_vars.rs index e38492d9e64..cb203e04f0c 100644 --- a/compiler/rustc_hir_analysis/src/collect/resolve_bound_vars.rs +++ b/compiler/rustc_hir_analysis/src/collect/resolve_bound_vars.rs @@ -1761,7 +1761,7 @@ impl<'a, 'tcx> BoundVarContext<'a, 'tcx> { break Some((bound_vars.into_iter().collect(), assoc_item)); } let predicates = tcx.explicit_supertraits_containing_assoc_item((def_id, assoc_name)); - let obligations = predicates.predicates.iter().filter_map(|&(pred, _)| { + let obligations = predicates.iter_identity_copied().filter_map(|(pred, _)| { let bound_predicate = pred.kind(); match bound_predicate.skip_binder() { ty::ClauseKind::Trait(data) => { diff --git a/compiler/rustc_hir_analysis/src/hir_ty_lowering/mod.rs b/compiler/rustc_hir_analysis/src/hir_ty_lowering/mod.rs index 0cdd3e4a1c6..98e1297ed06 100644 --- a/compiler/rustc_hir_analysis/src/hir_ty_lowering/mod.rs +++ b/compiler/rustc_hir_analysis/src/hir_ty_lowering/mod.rs @@ -136,7 +136,7 @@ pub trait HirTyLowerer<'tcx> { span: Span, def_id: LocalDefId, assoc_name: Ident, - ) -> ty::GenericPredicates<'tcx>; + ) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]>; /// Lower an associated type to a projection. /// @@ -831,13 +831,13 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { debug!(?ty_param_def_id, ?assoc_name, ?span); let tcx = self.tcx(); - let predicates = &self.probe_ty_param_bounds(span, ty_param_def_id, assoc_name).predicates; + let predicates = &self.probe_ty_param_bounds(span, ty_param_def_id, assoc_name); debug!("predicates={:#?}", predicates); self.probe_single_bound_for_assoc_item( || { let trait_refs = predicates - .iter() + .iter_identity_copied() .filter_map(|(p, _)| Some(p.as_trait_clause()?.map_bound(|t| t.trait_ref))); traits::transitive_bounds_that_define_assoc_item(tcx, trait_refs, assoc_name) }, diff --git a/compiler/rustc_hir_typeck/src/fn_ctxt/mod.rs b/compiler/rustc_hir_typeck/src/fn_ctxt/mod.rs index 8e69a075030..a43d7aa31a5 100644 --- a/compiler/rustc_hir_typeck/src/fn_ctxt/mod.rs +++ b/compiler/rustc_hir_typeck/src/fn_ctxt/mod.rs @@ -263,27 +263,24 @@ impl<'tcx> HirTyLowerer<'tcx> for FnCtxt<'_, 'tcx> { _: Span, def_id: LocalDefId, _: Ident, - ) -> ty::GenericPredicates<'tcx> { + ) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { let tcx = self.tcx; let item_def_id = tcx.hir().ty_param_owner(def_id); let generics = tcx.generics_of(item_def_id); let index = generics.param_def_id_to_index[&def_id.to_def_id()]; // HACK(eddyb) should get the original `Span`. let span = tcx.def_span(def_id); - ty::GenericPredicates { - parent: None, - predicates: tcx.arena.alloc_from_iter( - self.param_env.caller_bounds().iter().filter_map(|predicate| { - match predicate.kind().skip_binder() { - ty::ClauseKind::Trait(data) if data.self_ty().is_param(index) => { - Some((predicate, span)) - } - _ => None, + + ty::EarlyBinder::bind(tcx.arena.alloc_from_iter( + self.param_env.caller_bounds().iter().filter_map(|predicate| { + match predicate.kind().skip_binder() { + ty::ClauseKind::Trait(data) if data.self_ty().is_param(index) => { + Some((predicate, span)) } - }), - ), - effects_min_tys: ty::List::empty(), - } + _ => None, + } + }), + )) } fn lower_assoc_ty( diff --git a/compiler/rustc_infer/src/traits/util.rs b/compiler/rustc_infer/src/traits/util.rs index 335c65da054..3e4f9b48166 100644 --- a/compiler/rustc_infer/src/traits/util.rs +++ b/compiler/rustc_infer/src/traits/util.rs @@ -123,7 +123,7 @@ pub fn transitive_bounds_that_define_assoc_item<'tcx>( stack.extend( tcx.explicit_supertraits_containing_assoc_item((trait_ref.def_id(), assoc_name)) - .instantiate_own_identity() + .iter_identity_copied() .map(|(clause, _)| clause.instantiate_supertrait(tcx, trait_ref)) .filter_map(|clause| clause.as_trait_clause()) // FIXME: Negative supertraits are elaborated here lol diff --git a/compiler/rustc_lint/src/foreign_modules.rs b/compiler/rustc_lint/src/foreign_modules.rs index 5da1cbc2283..a60fc0ffbbb 100644 --- a/compiler/rustc_lint/src/foreign_modules.rs +++ b/compiler/rustc_lint/src/foreign_modules.rs @@ -265,8 +265,6 @@ fn structurally_same_type_impl<'tcx>( } else { // Do a full, depth-first comparison between the two. use rustc_type_ir::TyKind::*; - let a_kind = a.kind(); - let b_kind = b.kind(); let compare_layouts = |a, b| -> Result<bool, &'tcx LayoutError<'tcx>> { debug!("compare_layouts({:?}, {:?})", a, b); @@ -281,12 +279,11 @@ fn structurally_same_type_impl<'tcx>( Ok(a_layout == b_layout) }; - #[allow(rustc::usage_of_ty_tykind)] let is_primitive_or_pointer = - |kind: &ty::TyKind<'_>| kind.is_primitive() || matches!(kind, RawPtr(..) | Ref(..)); + |ty: Ty<'tcx>| ty.is_primitive() || matches!(ty.kind(), RawPtr(..) | Ref(..)); ensure_sufficient_stack(|| { - match (a_kind, b_kind) { + match (a.kind(), b.kind()) { (Adt(a_def, _), Adt(b_def, _)) => { // We can immediately rule out these types as structurally same if // their layouts differ. @@ -382,17 +379,21 @@ fn structurally_same_type_impl<'tcx>( // An Adt and a primitive or pointer type. This can be FFI-safe if non-null // enum layout optimisation is being applied. - (Adt(..), other_kind) | (other_kind, Adt(..)) - if is_primitive_or_pointer(other_kind) => - { - let (primitive, adt) = - if is_primitive_or_pointer(a.kind()) { (a, b) } else { (b, a) }; - if let Some(ty) = types::repr_nullable_ptr(tcx, param_env, adt, ckind) { - ty == primitive + (Adt(..), _) if is_primitive_or_pointer(b) => { + if let Some(ty) = types::repr_nullable_ptr(tcx, param_env, a, ckind) { + ty == b } else { compare_layouts(a, b).unwrap_or(false) } } + (_, Adt(..)) if is_primitive_or_pointer(a) => { + if let Some(ty) = types::repr_nullable_ptr(tcx, param_env, b, ckind) { + ty == a + } else { + compare_layouts(a, b).unwrap_or(false) + } + } + // Otherwise, just compare the layouts. This may fail to lint for some // incompatible types, but at the very least, will stop reads into // uninitialised memory. diff --git a/compiler/rustc_lint/src/multiple_supertrait_upcastable.rs b/compiler/rustc_lint/src/multiple_supertrait_upcastable.rs index 978109aba5f..78468020c4d 100644 --- a/compiler/rustc_lint/src/multiple_supertrait_upcastable.rs +++ b/compiler/rustc_lint/src/multiple_supertrait_upcastable.rs @@ -45,8 +45,7 @@ impl<'tcx> LateLintPass<'tcx> for MultipleSupertraitUpcastable { let direct_super_traits_iter = cx .tcx .explicit_super_predicates_of(def_id) - .predicates - .into_iter() + .iter_identity_copied() .filter_map(|(pred, _)| pred.as_trait_clause()); if direct_super_traits_iter.count() > 1 { cx.emit_span_lint( diff --git a/compiler/rustc_lint_defs/src/builtin.rs b/compiler/rustc_lint_defs/src/builtin.rs index 44c72e0c4fe..04fd7c9c627 100644 --- a/compiler/rustc_lint_defs/src/builtin.rs +++ b/compiler/rustc_lint_defs/src/builtin.rs @@ -4771,7 +4771,7 @@ declare_lint! { /// version of Rust this will be fixed and therefore dependencies relying /// on the non-spec-compliant C ABI will stop functioning. pub WASM_C_ABI, - Warn, + Deny, "detects dependencies that are incompatible with the Wasm C ABI", @future_incompatible = FutureIncompatibleInfo { reason: FutureIncompatibilityReason::FutureReleaseErrorReportInDeps, diff --git a/compiler/rustc_metadata/src/lib.rs b/compiler/rustc_metadata/src/lib.rs index c798ca00bcc..58b352f263d 100644 --- a/compiler/rustc_metadata/src/lib.rs +++ b/compiler/rustc_metadata/src/lib.rs @@ -3,6 +3,7 @@ #![allow(rustc::potential_query_instability)] #![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")] #![doc(rust_logo)] +#![feature(control_flow_enum)] #![feature(coroutines)] #![feature(decl_macro)] #![feature(error_iter)] @@ -35,7 +36,9 @@ pub mod locator; pub use creader::{load_symbol_from_dylib, DylibError}; pub use fs::{emit_wrapper_file, METADATA_FILENAME}; -pub use native_libs::find_native_static_library; +pub use native_libs::{ + find_native_static_library, try_find_native_static_library, walk_native_lib_search_dirs, +}; pub use rmeta::{encode_metadata, rendered_const, EncodedMetadata, METADATA_HEADER}; rustc_fluent_macro::fluent_messages! { "../messages.ftl" } diff --git a/compiler/rustc_metadata/src/native_libs.rs b/compiler/rustc_metadata/src/native_libs.rs index 34497f5ac53..a6ad449cb53 100644 --- a/compiler/rustc_metadata/src/native_libs.rs +++ b/compiler/rustc_metadata/src/native_libs.rs @@ -1,4 +1,5 @@ -use std::path::PathBuf; +use std::ops::ControlFlow; +use std::path::{Path, PathBuf}; use rustc_ast::{NestedMetaItem, CRATE_NODE_ID}; use rustc_attr as attr; @@ -16,10 +17,68 @@ use rustc_session::Session; use rustc_span::def_id::{DefId, LOCAL_CRATE}; use rustc_span::symbol::{sym, Symbol}; use rustc_target::spec::abi::Abi; +use rustc_target::spec::LinkSelfContainedComponents; use crate::{errors, fluent_generated}; -pub fn find_native_static_library(name: &str, verbatim: bool, sess: &Session) -> PathBuf { +pub fn walk_native_lib_search_dirs<R>( + sess: &Session, + self_contained_components: LinkSelfContainedComponents, + apple_sdk_root: Option<&Path>, + mut f: impl FnMut(&Path, bool /*is_framework*/) -> ControlFlow<R>, +) -> ControlFlow<R> { + // Library search paths explicitly supplied by user (`-L` on the command line). + for search_path in sess.target_filesearch(PathKind::Native).cli_search_paths() { + f(&search_path.dir, false)?; + } + for search_path in sess.target_filesearch(PathKind::Framework).cli_search_paths() { + // Frameworks are looked up strictly in framework-specific paths. + if search_path.kind != PathKind::All { + f(&search_path.dir, true)?; + } + } + + // The toolchain ships some native library components and self-contained linking was enabled. + // Add the self-contained library directory to search paths. + if self_contained_components.intersects( + LinkSelfContainedComponents::LIBC + | LinkSelfContainedComponents::UNWIND + | LinkSelfContainedComponents::MINGW, + ) { + f(&sess.target_tlib_path.dir.join("self-contained"), false)?; + } + + // Toolchains for some targets may ship `libunwind.a`, but place it into the main sysroot + // library directory instead of the self-contained directories. + // Sanitizer libraries have the same issue and are also linked by name on Apple targets. + // The targets here should be in sync with `copy_third_party_objects` in bootstrap. + // FIXME: implement `-Clink-self-contained=+/-unwind,+/-sanitizers`, move the shipped libunwind + // and sanitizers to self-contained directory, and stop adding this search path. + if sess.target.vendor == "fortanix" + || sess.target.os == "linux" + || sess.target.os == "fuchsia" + || sess.target.is_like_osx && !sess.opts.unstable_opts.sanitizer.is_empty() + { + f(&sess.target_tlib_path.dir, false)?; + } + + // Mac Catalyst uses the macOS SDK, but to link to iOS-specific frameworks + // we must have the support library stubs in the library search path (#121430). + if let Some(sdk_root) = apple_sdk_root + && sess.target.llvm_target.contains("macabi") + { + f(&sdk_root.join("System/iOSSupport/usr/lib"), false)?; + f(&sdk_root.join("System/iOSSupport/System/Library/Frameworks"), true)?; + } + + ControlFlow::Continue(()) +} + +pub fn try_find_native_static_library( + sess: &Session, + name: &str, + verbatim: bool, +) -> Option<PathBuf> { let formats = if verbatim { vec![("".into(), "".into())] } else { @@ -30,16 +89,29 @@ pub fn find_native_static_library(name: &str, verbatim: bool, sess: &Session) -> if os == unix { vec![os] } else { vec![os, unix] } }; - for path in sess.target_filesearch(PathKind::Native).search_paths() { - for (prefix, suffix) in &formats { - let test = path.dir.join(format!("{prefix}{name}{suffix}")); - if test.exists() { - return test; + // FIXME: Account for self-contained linking settings and Apple SDK. + walk_native_lib_search_dirs( + sess, + LinkSelfContainedComponents::empty(), + None, + |dir, is_framework| { + if !is_framework { + for (prefix, suffix) in &formats { + let test = dir.join(format!("{prefix}{name}{suffix}")); + if test.exists() { + return ControlFlow::Break(test); + } + } } - } - } + ControlFlow::Continue(()) + }, + ) + .break_value() +} - sess.dcx().emit_fatal(errors::MissingNativeLibrary::new(name, verbatim)); +pub fn find_native_static_library(name: &str, verbatim: bool, sess: &Session) -> PathBuf { + try_find_native_static_library(sess, name, verbatim) + .unwrap_or_else(|| sess.dcx().emit_fatal(errors::MissingNativeLibrary::new(name, verbatim))) } fn find_bundled_library( diff --git a/compiler/rustc_metadata/src/rmeta/decoder.rs b/compiler/rustc_metadata/src/rmeta/decoder.rs index 09aea233718..f3ae24a5895 100644 --- a/compiler/rustc_metadata/src/rmeta/decoder.rs +++ b/compiler/rustc_metadata/src/rmeta/decoder.rs @@ -1070,34 +1070,6 @@ impl<'a> CrateMetadataRef<'a> { ) } - fn get_explicit_item_bounds<'tcx>( - self, - index: DefIndex, - tcx: TyCtxt<'tcx>, - ) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { - let lazy = self.root.tables.explicit_item_bounds.get(self, index); - let output = if lazy.is_default() { - &mut [] - } else { - tcx.arena.alloc_from_iter(lazy.decode((self, tcx))) - }; - ty::EarlyBinder::bind(&*output) - } - - fn get_explicit_item_super_predicates<'tcx>( - self, - index: DefIndex, - tcx: TyCtxt<'tcx>, - ) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { - let lazy = self.root.tables.explicit_item_super_predicates.get(self, index); - let output = if lazy.is_default() { - &mut [] - } else { - tcx.arena.alloc_from_iter(lazy.decode((self, tcx))) - }; - ty::EarlyBinder::bind(&*output) - } - fn get_variant( self, kind: DefKind, @@ -1323,10 +1295,6 @@ impl<'a> CrateMetadataRef<'a> { self.root.tables.optimized_mir.get(self, id).is_some() } - fn cross_crate_inlinable(self, id: DefIndex) -> bool { - self.root.tables.cross_crate_inlinable.get(self, id) - } - fn get_fn_has_self_parameter(self, id: DefIndex, sess: &'a Session) -> bool { self.root .tables diff --git a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs index 27625f79108..a82340e3d61 100644 --- a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs +++ b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs @@ -32,13 +32,20 @@ trait ProcessQueryValue<'tcx, T> { fn process_decoded(self, _tcx: TyCtxt<'tcx>, _err: impl Fn() -> !) -> T; } -impl<T> ProcessQueryValue<'_, Option<T>> for Option<T> { +impl<T> ProcessQueryValue<'_, T> for T { #[inline(always)] - fn process_decoded(self, _tcx: TyCtxt<'_>, _err: impl Fn() -> !) -> Option<T> { + fn process_decoded(self, _tcx: TyCtxt<'_>, _err: impl Fn() -> !) -> T { self } } +impl<'tcx, T> ProcessQueryValue<'tcx, ty::EarlyBinder<'tcx, T>> for T { + #[inline(always)] + fn process_decoded(self, _tcx: TyCtxt<'_>, _err: impl Fn() -> !) -> ty::EarlyBinder<'tcx, T> { + ty::EarlyBinder::bind(self) + } +} + impl<T> ProcessQueryValue<'_, T> for Option<T> { #[inline(always)] fn process_decoded(self, _tcx: TyCtxt<'_>, err: impl Fn() -> !) -> T { @@ -70,6 +77,24 @@ impl<'a, 'tcx, T: Copy + Decodable<DecodeContext<'a, 'tcx>>> ProcessQueryValue<' } impl<'a, 'tcx, T: Copy + Decodable<DecodeContext<'a, 'tcx>>> + ProcessQueryValue<'tcx, ty::EarlyBinder<'tcx, &'tcx [T]>> + for Option<DecodeIterator<'a, 'tcx, T>> +{ + #[inline(always)] + fn process_decoded( + self, + tcx: TyCtxt<'tcx>, + _err: impl Fn() -> !, + ) -> ty::EarlyBinder<'tcx, &'tcx [T]> { + ty::EarlyBinder::bind(if let Some(iter) = self { + tcx.arena.alloc_from_iter(iter) + } else { + &[] + }) + } +} + +impl<'a, 'tcx, T: Copy + Decodable<DecodeContext<'a, 'tcx>>> ProcessQueryValue<'tcx, Option<&'tcx [T]>> for Option<DecodeIterator<'a, 'tcx, T>> { #[inline(always)] @@ -103,7 +128,12 @@ macro_rules! provide_one { provide_one! { $tcx, $def_id, $other, $cdata, $name => { let lazy = $cdata.root.tables.$name.get($cdata, $def_id.index); - if lazy.is_default() { &[] } else { $tcx.arena.alloc_from_iter(lazy.decode(($cdata, $tcx))) } + let value = if lazy.is_default() { + &[] as &[_] + } else { + $tcx.arena.alloc_from_iter(lazy.decode(($cdata, $tcx))) + }; + value.process_decoded($tcx, || panic!("{:?} does not have a {:?}", $def_id, stringify!($name))) } } }; @@ -212,15 +242,15 @@ impl IntoArgs for (CrateNum, SimplifiedType) { } provide! { tcx, def_id, other, cdata, - explicit_item_bounds => { cdata.get_explicit_item_bounds(def_id.index, tcx) } - explicit_item_super_predicates => { cdata.get_explicit_item_super_predicates(def_id.index, tcx) } + explicit_item_bounds => { table_defaulted_array } + explicit_item_super_predicates => { table_defaulted_array } explicit_predicates_of => { table } generics_of => { table } inferred_outlives_of => { table_defaulted_array } explicit_super_predicates_of => { table } explicit_implied_predicates_of => { table } type_of => { table } - type_alias_is_lazy => { cdata.root.tables.type_alias_is_lazy.get(cdata, def_id.index) } + type_alias_is_lazy => { table_direct } variances_of => { table } fn_sig => { table } codegen_fn_attrs => { table } @@ -241,7 +271,7 @@ provide! { tcx, def_id, other, cdata, lookup_default_body_stability => { table } lookup_deprecation_entry => { table } params_in_repr => { table } - unused_generic_params => { cdata.root.tables.unused_generic_params.get(cdata, def_id.index) } + unused_generic_params => { table_direct } def_kind => { cdata.def_kind(def_id.index) } impl_parent => { table } defaultness => { table_direct } @@ -287,9 +317,7 @@ provide! { tcx, def_id, other, cdata, .process_decoded(tcx, || panic!("{def_id:?} does not have trait_impl_trait_tys"))) } - associated_type_for_effects => { - table - } + associated_type_for_effects => { table } associated_types_for_impl_traits_in_associated_fn => { table_defaulted_array } visibility => { cdata.get_visibility(def_id.index) } @@ -310,7 +338,7 @@ provide! { tcx, def_id, other, cdata, item_attrs => { tcx.arena.alloc_from_iter(cdata.get_item_attrs(def_id.index, tcx.sess)) } is_mir_available => { cdata.is_item_mir_available(def_id.index) } is_ctfe_mir_available => { cdata.is_ctfe_mir_available(def_id.index) } - cross_crate_inlinable => { cdata.cross_crate_inlinable(def_id.index) } + cross_crate_inlinable => { table_direct } dylib_dependency_formats => { cdata.get_dylib_dependency_formats(tcx) } is_private_dep => { cdata.private_dep } diff --git a/compiler/rustc_metadata/src/rmeta/encoder.rs b/compiler/rustc_metadata/src/rmeta/encoder.rs index d9a844ad837..919623cff60 100644 --- a/compiler/rustc_metadata/src/rmeta/encoder.rs +++ b/compiler/rustc_metadata/src/rmeta/encoder.rs @@ -1446,8 +1446,10 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> { } if let DefKind::Trait = def_kind { record!(self.tables.trait_def[def_id] <- self.tcx.trait_def(def_id)); - record!(self.tables.explicit_super_predicates_of[def_id] <- self.tcx.explicit_super_predicates_of(def_id)); - record!(self.tables.explicit_implied_predicates_of[def_id] <- self.tcx.explicit_implied_predicates_of(def_id)); + record_array!(self.tables.explicit_super_predicates_of[def_id] <- + self.tcx.explicit_super_predicates_of(def_id).skip_binder()); + record_array!(self.tables.explicit_implied_predicates_of[def_id] <- + self.tcx.explicit_implied_predicates_of(def_id).skip_binder()); let module_children = self.tcx.module_children_local(local_id); record_array!(self.tables.module_children_non_reexports[def_id] <- @@ -1455,8 +1457,10 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> { } if let DefKind::TraitAlias = def_kind { record!(self.tables.trait_def[def_id] <- self.tcx.trait_def(def_id)); - record!(self.tables.explicit_super_predicates_of[def_id] <- self.tcx.explicit_super_predicates_of(def_id)); - record!(self.tables.explicit_implied_predicates_of[def_id] <- self.tcx.explicit_implied_predicates_of(def_id)); + record_array!(self.tables.explicit_super_predicates_of[def_id] <- + self.tcx.explicit_super_predicates_of(def_id).skip_binder()); + record_array!(self.tables.explicit_implied_predicates_of[def_id] <- + self.tcx.explicit_implied_predicates_of(def_id).skip_binder()); } if let DefKind::Trait | DefKind::Impl { .. } = def_kind { let associated_item_def_ids = self.tcx.associated_item_def_ids(def_id); diff --git a/compiler/rustc_metadata/src/rmeta/mod.rs b/compiler/rustc_metadata/src/rmeta/mod.rs index aec728d4262..987ee3f07e9 100644 --- a/compiler/rustc_metadata/src/rmeta/mod.rs +++ b/compiler/rustc_metadata/src/rmeta/mod.rs @@ -419,10 +419,10 @@ define_tables! { lookup_deprecation_entry: Table<DefIndex, LazyValue<attr::Deprecation>>, explicit_predicates_of: Table<DefIndex, LazyValue<ty::GenericPredicates<'static>>>, generics_of: Table<DefIndex, LazyValue<ty::Generics>>, - explicit_super_predicates_of: Table<DefIndex, LazyValue<ty::GenericPredicates<'static>>>, + explicit_super_predicates_of: Table<DefIndex, LazyArray<(ty::Clause<'static>, Span)>>, // As an optimization, we only store this for trait aliases, // since it's identical to explicit_super_predicates_of for traits. - explicit_implied_predicates_of: Table<DefIndex, LazyValue<ty::GenericPredicates<'static>>>, + explicit_implied_predicates_of: Table<DefIndex, LazyArray<(ty::Clause<'static>, Span)>>, type_of: Table<DefIndex, LazyValue<ty::EarlyBinder<'static, Ty<'static>>>>, variances_of: Table<DefIndex, LazyArray<ty::Variance>>, fn_sig: Table<DefIndex, LazyValue<ty::EarlyBinder<'static, ty::PolyFnSig<'static>>>>, diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs index 6434bd0d7bf..b6443778c93 100644 --- a/compiler/rustc_middle/src/query/mod.rs +++ b/compiler/rustc_middle/src/query/mod.rs @@ -651,7 +651,7 @@ rustc_queries! { /// is a subset of the full list of predicates. We store these in a separate map /// because we must evaluate them even during type conversion, often before the full /// predicates are available (note that super-predicates must not be cyclic). - query explicit_super_predicates_of(key: DefId) -> ty::GenericPredicates<'tcx> { + query explicit_super_predicates_of(key: DefId) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { desc { |tcx| "computing the super predicates of `{}`", tcx.def_path_str(key) } cache_on_disk_if { key.is_local() } separate_provide_extern @@ -662,7 +662,7 @@ rustc_queries! { /// of the trait. For regular traits, this includes all super-predicates and their /// associated type bounds. For trait aliases, currently, this includes all of the /// predicates of the trait alias. - query explicit_implied_predicates_of(key: DefId) -> ty::GenericPredicates<'tcx> { + query explicit_implied_predicates_of(key: DefId) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { desc { |tcx| "computing the implied predicates of `{}`", tcx.def_path_str(key) } cache_on_disk_if { key.is_local() } separate_provide_extern @@ -671,7 +671,9 @@ rustc_queries! { /// The Ident is the name of an associated type.The query returns only the subset /// of supertraits that define the given associated type. This is used to avoid /// cycles in resolving type-dependent associated item paths like `T::Item`. - query explicit_supertraits_containing_assoc_item(key: (DefId, rustc_span::symbol::Ident)) -> ty::GenericPredicates<'tcx> { + query explicit_supertraits_containing_assoc_item( + key: (DefId, rustc_span::symbol::Ident) + ) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { desc { |tcx| "computing the super traits of `{}` with associated type name `{}`", tcx.def_path_str(key.0), key.1 @@ -680,7 +682,9 @@ rustc_queries! { /// To avoid cycles within the predicates of a single item we compute /// per-type-parameter predicates for resolving `T::AssocTy`. - query type_param_predicates(key: (LocalDefId, LocalDefId, rustc_span::symbol::Ident)) -> ty::GenericPredicates<'tcx> { + query type_param_predicates( + key: (LocalDefId, LocalDefId, rustc_span::symbol::Ident) + ) -> ty::EarlyBinder<'tcx, &'tcx [(ty::Clause<'tcx>, Span)]> { desc { |tcx| "computing the bounds for type parameter `{}`", tcx.hir().ty_param_name(key.1) } } diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs index 70df205d893..d6dbad9dab8 100644 --- a/compiler/rustc_middle/src/ty/context.rs +++ b/compiler/rustc_middle/src/ty/context.rs @@ -349,16 +349,14 @@ impl<'tcx> Interner for TyCtxt<'tcx> { self, def_id: DefId, ) -> ty::EarlyBinder<'tcx, impl IntoIterator<Item = (ty::Clause<'tcx>, Span)>> { - ty::EarlyBinder::bind(self.explicit_super_predicates_of(def_id).instantiate_identity(self)) + self.explicit_super_predicates_of(def_id).map_bound(|preds| preds.into_iter().copied()) } fn explicit_implied_predicates_of( self, def_id: DefId, ) -> ty::EarlyBinder<'tcx, impl IntoIterator<Item = (ty::Clause<'tcx>, Span)>> { - ty::EarlyBinder::bind( - self.explicit_implied_predicates_of(def_id).instantiate_identity(self), - ) + self.explicit_implied_predicates_of(def_id).map_bound(|preds| preds.into_iter().copied()) } fn has_target_features(self, def_id: DefId) -> bool { diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs index d60bfb9faa1..c6621a7a643 100644 --- a/compiler/rustc_middle/src/ty/sty.rs +++ b/compiler/rustc_middle/src/ty/sty.rs @@ -1000,7 +1000,7 @@ impl<'tcx> Ty<'tcx> { #[inline] pub fn is_primitive(self) -> bool { - self.kind().is_primitive() + matches!(self.kind(), Bool | Char | Int(_) | Uint(_) | Float(_)) } #[inline] diff --git a/compiler/rustc_mir_transform/src/dataflow_const_prop.rs b/compiler/rustc_mir_transform/src/dataflow_const_prop.rs index f207216d6f4..03b1d426df4 100644 --- a/compiler/rustc_mir_transform/src/dataflow_const_prop.rs +++ b/compiler/rustc_mir_transform/src/dataflow_const_prop.rs @@ -382,7 +382,7 @@ impl<'a, 'tcx> ConstAnalysis<'a, 'tcx> { place: PlaceIndex, mut operand: OpTy<'tcx>, projection: &[PlaceElem<'tcx>], - ) -> Option<!> { + ) { for &(mut proj_elem) in projection { if let PlaceElem::Index(index) = proj_elem { if let FlatSet::Elem(index) = state.get(index.into(), &self.map) @@ -391,10 +391,14 @@ impl<'a, 'tcx> ConstAnalysis<'a, 'tcx> { { proj_elem = PlaceElem::ConstantIndex { offset, min_length, from_end: false }; } else { - return None; + return; } } - operand = self.ecx.project(&operand, proj_elem).ok()?; + operand = if let Ok(operand) = self.ecx.project(&operand, proj_elem) { + operand + } else { + return; + } } self.map.for_each_projection_value( @@ -426,8 +430,6 @@ impl<'a, 'tcx> ConstAnalysis<'a, 'tcx> { } }, ); - - None } fn binary_op( diff --git a/compiler/rustc_mir_transform/src/jump_threading.rs b/compiler/rustc_mir_transform/src/jump_threading.rs index 96c52845a4a..8997b1d57cd 100644 --- a/compiler/rustc_mir_transform/src/jump_threading.rs +++ b/compiler/rustc_mir_transform/src/jump_threading.rs @@ -191,26 +191,26 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { /// Recursion entry point to find threading opportunities. #[instrument(level = "trace", skip(self))] - fn start_from_switch(&mut self, bb: BasicBlock) -> Option<!> { + fn start_from_switch(&mut self, bb: BasicBlock) { let bbdata = &self.body[bb]; if bbdata.is_cleanup || self.loop_headers.contains(bb) { - return None; + return; } - let (discr, targets) = bbdata.terminator().kind.as_switch()?; - let discr = discr.place()?; + let Some((discr, targets)) = bbdata.terminator().kind.as_switch() else { return }; + let Some(discr) = discr.place() else { return }; debug!(?discr, ?bb); let discr_ty = discr.ty(self.body, self.tcx).ty; - let discr_layout = self.ecx.layout_of(discr_ty).ok()?; + let Ok(discr_layout) = self.ecx.layout_of(discr_ty) else { return }; - let discr = self.map.find(discr.as_ref())?; + let Some(discr) = self.map.find(discr.as_ref()) else { return }; debug!(?discr); let cost = CostChecker::new(self.tcx, self.param_env, None, self.body); let mut state = State::new_reachable(); let conds = if let Some((value, then, else_)) = targets.as_static_if() { - let value = ScalarInt::try_from_uint(value, discr_layout.size)?; + let Some(value) = ScalarInt::try_from_uint(value, discr_layout.size) else { return }; self.arena.alloc_from_iter([ Condition { value, polarity: Polarity::Eq, target: then }, Condition { value, polarity: Polarity::Ne, target: else_ }, @@ -225,7 +225,6 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { state.insert_value_idx(discr, conds, self.map); self.find_opportunity(bb, state, cost, 0); - None } /// Recursively walk statements backwards from this bb's terminator to find threading @@ -364,18 +363,17 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { lhs: PlaceIndex, rhs: ImmTy<'tcx>, state: &mut State<ConditionSet<'a>>, - ) -> Option<!> { + ) { let register_opportunity = |c: Condition| { debug!(?bb, ?c.target, "register"); self.opportunities.push(ThreadingOpportunity { chain: vec![bb], target: c.target }) }; - let conditions = state.try_get_idx(lhs, self.map)?; - if let Immediate::Scalar(Scalar::Int(int)) = *rhs { + if let Some(conditions) = state.try_get_idx(lhs, self.map) + && let Immediate::Scalar(Scalar::Int(int)) = *rhs + { conditions.iter_matches(int).for_each(register_opportunity); } - - None } /// If we expect `lhs ?= A`, we have an opportunity if we assume `constant == A`. @@ -428,22 +426,23 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { lhs: PlaceIndex, rhs: &Operand<'tcx>, state: &mut State<ConditionSet<'a>>, - ) -> Option<!> { + ) { match rhs { // If we expect `lhs ?= A`, we have an opportunity if we assume `constant == A`. Operand::Constant(constant) => { - let constant = - self.ecx.eval_mir_constant(&constant.const_, constant.span, None).ok()?; + let Ok(constant) = + self.ecx.eval_mir_constant(&constant.const_, constant.span, None) + else { + return; + }; self.process_constant(bb, lhs, constant, state); } // Transfer the conditions on the copied rhs. Operand::Move(rhs) | Operand::Copy(rhs) => { - let rhs = self.map.find(rhs.as_ref())?; + let Some(rhs) = self.map.find(rhs.as_ref()) else { return }; state.insert_place_idx(rhs, lhs, self.map); } } - - None } #[instrument(level = "trace", skip(self))] @@ -453,16 +452,14 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { lhs_place: &Place<'tcx>, rhs: &Rvalue<'tcx>, state: &mut State<ConditionSet<'a>>, - ) -> Option<!> { - let lhs = self.map.find(lhs_place.as_ref())?; + ) { + let Some(lhs) = self.map.find(lhs_place.as_ref()) else { return }; match rhs { - Rvalue::Use(operand) => self.process_operand(bb, lhs, operand, state)?, + Rvalue::Use(operand) => self.process_operand(bb, lhs, operand, state), // Transfer the conditions on the copy rhs. - Rvalue::CopyForDeref(rhs) => { - self.process_operand(bb, lhs, &Operand::Copy(*rhs), state)? - } + Rvalue::CopyForDeref(rhs) => self.process_operand(bb, lhs, &Operand::Copy(*rhs), state), Rvalue::Discriminant(rhs) => { - let rhs = self.map.find_discr(rhs.as_ref())?; + let Some(rhs) = self.map.find_discr(rhs.as_ref()) else { return }; state.insert_place_idx(rhs, lhs, self.map); } // If we expect `lhs ?= A`, we have an opportunity if we assume `constant == A`. @@ -470,7 +467,7 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { let agg_ty = lhs_place.ty(self.body, self.tcx).ty; let lhs = match kind { // Do not support unions. - AggregateKind::Adt(.., Some(_)) => return None, + AggregateKind::Adt(.., Some(_)) => return, AggregateKind::Adt(_, variant_index, ..) if agg_ty.is_enum() => { if let Some(discr_target) = self.map.apply(lhs, TrackElem::Discriminant) && let Ok(discr_value) = @@ -478,7 +475,11 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { { self.process_immediate(bb, discr_target, discr_value, state); } - self.map.apply(lhs, TrackElem::Variant(*variant_index))? + if let Some(idx) = self.map.apply(lhs, TrackElem::Variant(*variant_index)) { + idx + } else { + return; + } } _ => lhs, }; @@ -490,8 +491,8 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { } // Transfer the conditions on the copy rhs, after inversing polarity. Rvalue::UnaryOp(UnOp::Not, Operand::Move(place) | Operand::Copy(place)) => { - let conditions = state.try_get_idx(lhs, self.map)?; - let place = self.map.find(place.as_ref())?; + let Some(conditions) = state.try_get_idx(lhs, self.map) else { return }; + let Some(place) = self.map.find(place.as_ref()) else { return }; let conds = conditions.map(self.arena, Condition::inv); state.insert_value_idx(place, conds, self.map); } @@ -502,21 +503,25 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { box (Operand::Move(place) | Operand::Copy(place), Operand::Constant(value)) | box (Operand::Constant(value), Operand::Move(place) | Operand::Copy(place)), ) => { - let conditions = state.try_get_idx(lhs, self.map)?; - let place = self.map.find(place.as_ref())?; + let Some(conditions) = state.try_get_idx(lhs, self.map) else { return }; + let Some(place) = self.map.find(place.as_ref()) else { return }; let equals = match op { BinOp::Eq => ScalarInt::TRUE, BinOp::Ne => ScalarInt::FALSE, - _ => return None, + _ => return, }; if value.const_.ty().is_floating_point() { // Floating point equality does not follow bit-patterns. // -0.0 and NaN both have special rules for equality, // and therefore we cannot use integer comparisons for them. // Avoid handling them, though this could be extended in the future. - return None; + return; } - let value = value.const_.normalize(self.tcx, self.param_env).try_to_scalar_int()?; + let Some(value) = + value.const_.normalize(self.tcx, self.param_env).try_to_scalar_int() + else { + return; + }; let conds = conditions.map(self.arena, |c| Condition { value, polarity: if c.matches(equals) { Polarity::Eq } else { Polarity::Ne }, @@ -527,8 +532,6 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { _ => {} } - - None } #[instrument(level = "trace", skip(self))] @@ -537,7 +540,7 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { bb: BasicBlock, stmt: &Statement<'tcx>, state: &mut State<ConditionSet<'a>>, - ) -> Option<!> { + ) { let register_opportunity = |c: Condition| { debug!(?bb, ?c.target, "register"); self.opportunities.push(ThreadingOpportunity { chain: vec![bb], target: c.target }) @@ -550,12 +553,12 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { // If we expect `discriminant(place) ?= A`, // we have an opportunity if `variant_index ?= A`. StatementKind::SetDiscriminant { box place, variant_index } => { - let discr_target = self.map.find_discr(place.as_ref())?; + let Some(discr_target) = self.map.find_discr(place.as_ref()) else { return }; let enum_ty = place.ty(self.body, self.tcx).ty; // `SetDiscriminant` may be a no-op if the assigned variant is the untagged variant // of a niche encoding. If we cannot ensure that we write to the discriminant, do // nothing. - let enum_layout = self.ecx.layout_of(enum_ty).ok()?; + let Ok(enum_layout) = self.ecx.layout_of(enum_ty) else { return }; let writes_discriminant = match enum_layout.variants { Variants::Single { index } => { assert_eq!(index, *variant_index); @@ -568,24 +571,25 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { } => *variant_index != untagged_variant, }; if writes_discriminant { - let discr = self.ecx.discriminant_for_variant(enum_ty, *variant_index).ok()?; - self.process_immediate(bb, discr_target, discr, state)?; + let Ok(discr) = self.ecx.discriminant_for_variant(enum_ty, *variant_index) + else { + return; + }; + self.process_immediate(bb, discr_target, discr, state); } } // If we expect `lhs ?= true`, we have an opportunity if we assume `lhs == true`. StatementKind::Intrinsic(box NonDivergingIntrinsic::Assume( Operand::Copy(place) | Operand::Move(place), )) => { - let conditions = state.try_get(place.as_ref(), self.map)?; + let Some(conditions) = state.try_get(place.as_ref(), self.map) else { return }; conditions.iter_matches(ScalarInt::TRUE).for_each(register_opportunity); } StatementKind::Assign(box (lhs_place, rhs)) => { - self.process_assign(bb, lhs_place, rhs, state)?; + self.process_assign(bb, lhs_place, rhs, state); } _ => {} } - - None } #[instrument(level = "trace", skip(self, state, cost))] @@ -638,17 +642,17 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { targets: &SwitchTargets, target_bb: BasicBlock, state: &mut State<ConditionSet<'a>>, - ) -> Option<!> { + ) { debug_assert_ne!(target_bb, START_BLOCK); debug_assert_eq!(self.body.basic_blocks.predecessors()[target_bb].len(), 1); - let discr = discr.place()?; + let Some(discr) = discr.place() else { return }; let discr_ty = discr.ty(self.body, self.tcx).ty; - let discr_layout = self.ecx.layout_of(discr_ty).ok()?; - let conditions = state.try_get(discr.as_ref(), self.map)?; + let Ok(discr_layout) = self.ecx.layout_of(discr_ty) else { return }; + let Some(conditions) = state.try_get(discr.as_ref(), self.map) else { return }; if let Some((value, _)) = targets.iter().find(|&(_, target)| target == target_bb) { - let value = ScalarInt::try_from_uint(value, discr_layout.size)?; + let Some(value) = ScalarInt::try_from_uint(value, discr_layout.size) else { return }; debug_assert_eq!(targets.iter().filter(|&(_, target)| target == target_bb).count(), 1); // We are inside `target_bb`. Since we have a single predecessor, we know we passed @@ -662,7 +666,7 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { } else if let Some((value, _, else_bb)) = targets.as_static_if() && target_bb == else_bb { - let value = ScalarInt::try_from_uint(value, discr_layout.size)?; + let Some(value) = ScalarInt::try_from_uint(value, discr_layout.size) else { return }; // We only know that `discr != value`. That's much weaker information than // the equality we had in the previous arm. All we can conclude is that @@ -675,8 +679,6 @@ impl<'tcx, 'a> TOFinder<'tcx, 'a> { } } } - - None } } diff --git a/compiler/rustc_mir_transform/src/known_panics_lint.rs b/compiler/rustc_mir_transform/src/known_panics_lint.rs index 7eed47cf239..3427b93c1f6 100644 --- a/compiler/rustc_mir_transform/src/known_panics_lint.rs +++ b/compiler/rustc_mir_transform/src/known_panics_lint.rs @@ -469,12 +469,12 @@ impl<'mir, 'tcx> ConstPropagator<'mir, 'tcx> { msg: &AssertKind<Operand<'tcx>>, cond: &Operand<'tcx>, location: Location, - ) -> Option<!> { - let value = &self.eval_operand(cond)?; + ) { + let Some(value) = &self.eval_operand(cond) else { return }; trace!("assertion on {:?} should be {:?}", value, expected); let expected = Scalar::from_bool(expected); - let value_const = self.use_ecx(|this| this.ecx.read_scalar(value))?; + let Some(value_const) = self.use_ecx(|this| this.ecx.read_scalar(value)) else { return }; if expected != value_const { // Poison all places this operand references so that further code @@ -516,14 +516,12 @@ impl<'mir, 'tcx> ConstPropagator<'mir, 'tcx> { AssertKind::BoundsCheck { len, index } } // Remaining overflow errors are already covered by checks on the binary operators. - AssertKind::Overflow(..) | AssertKind::OverflowNeg(_) => return None, + AssertKind::Overflow(..) | AssertKind::OverflowNeg(_) => return, // Need proper const propagator for these. - _ => return None, + _ => return, }; self.report_assert_as_lint(location, AssertLintKind::UnconditionalPanic, msg); } - - None } fn ensure_not_propagated(&self, local: Local) { diff --git a/compiler/rustc_parse/src/parser/nonterminal.rs b/compiler/rustc_parse/src/parser/nonterminal.rs index 999f6f0eeb0..e66d0df012b 100644 --- a/compiler/rustc_parse/src/parser/nonterminal.rs +++ b/compiler/rustc_parse/src/parser/nonterminal.rs @@ -86,25 +86,7 @@ impl<'a> Parser<'a> { token::Interpolated(nt) => may_be_ident(nt), _ => false, }, - NonterminalKind::Pat(pat_kind) => match &token.kind { - // box, ref, mut, and other identifiers (can stricten) - token::Ident(..) | token::NtIdent(..) | - token::OpenDelim(Delimiter::Parenthesis) | // tuple pattern - token::OpenDelim(Delimiter::Bracket) | // slice pattern - token::BinOp(token::And) | // reference - token::BinOp(token::Minus) | // negative literal - token::AndAnd | // double reference - token::Literal(_) | // literal - token::DotDot | // range pattern (future compat) - token::DotDotDot | // range pattern (future compat) - token::PathSep | // path - token::Lt | // path (UFCS constant) - token::BinOp(token::Shl) => true, // path (double UFCS) - // leading vert `|` or-pattern - token::BinOp(token::Or) => matches!(pat_kind, PatWithOr), - token::Interpolated(nt) => may_be_ident(nt), - _ => false, - }, + NonterminalKind::Pat(pat_kind) => token.can_begin_pattern(pat_kind), NonterminalKind::Lifetime => match &token.kind { token::Lifetime(_) | token::NtLifetime(..) => true, _ => false, diff --git a/compiler/rustc_parse/src/parser/pat.rs b/compiler/rustc_parse/src/parser/pat.rs index cc68ae237ba..8233f9a7943 100644 --- a/compiler/rustc_parse/src/parser/pat.rs +++ b/compiler/rustc_parse/src/parser/pat.rs @@ -444,7 +444,11 @@ impl<'a> Parser<'a> { let mut lo = self.token.span; - if self.token.is_keyword(kw::Let) && self.look_ahead(1, |tok| tok.can_begin_pattern()) { + if self.token.is_keyword(kw::Let) + && self.look_ahead(1, |tok| { + tok.can_begin_pattern(token::NtPatKind::PatParam { inferred: false }) + }) + { self.bump(); self.dcx().emit_err(RemoveLet { span: lo }); lo = self.token.span; diff --git a/compiler/rustc_parse/src/parser/path.rs b/compiler/rustc_parse/src/parser/path.rs index d8bf10e6021..8ee40ecd77e 100644 --- a/compiler/rustc_parse/src/parser/path.rs +++ b/compiler/rustc_parse/src/parser/path.rs @@ -378,7 +378,10 @@ impl<'a> Parser<'a> { if self.may_recover() && prev_token_before_parsing == token::PathSep && (style == PathStyle::Expr && self.token.can_begin_expr() - || style == PathStyle::Pat && self.token.can_begin_pattern()) + || style == PathStyle::Pat + && self.token.can_begin_pattern(token::NtPatKind::PatParam { + inferred: false, + })) { snapshot = Some(self.create_snapshot_for_diagnostic()); } diff --git a/compiler/rustc_trait_selection/src/traits/object_safety.rs b/compiler/rustc_trait_selection/src/traits/object_safety.rs index 8e1fc0d7fe6..eb01151baae 100644 --- a/compiler/rustc_trait_selection/src/traits/object_safety.rs +++ b/compiler/rustc_trait_selection/src/traits/object_safety.rs @@ -185,12 +185,11 @@ fn predicates_reference_self( ) -> SmallVec<[Span; 1]> { let trait_ref = ty::Binder::dummy(ty::TraitRef::identity(tcx, trait_def_id)); let predicates = if supertraits_only { - tcx.explicit_super_predicates_of(trait_def_id) + tcx.explicit_super_predicates_of(trait_def_id).skip_binder() } else { - tcx.predicates_of(trait_def_id) + tcx.predicates_of(trait_def_id).predicates }; predicates - .predicates .iter() .map(|&(predicate, sp)| (predicate.instantiate_supertrait(tcx, trait_ref), sp)) .filter_map(|(clause, sp)| { @@ -266,9 +265,8 @@ fn super_predicates_have_non_lifetime_binders( return SmallVec::new(); } tcx.explicit_super_predicates_of(trait_def_id) - .predicates - .iter() - .filter_map(|(pred, span)| pred.has_non_region_bound_vars().then_some(*span)) + .iter_identity_copied() + .filter_map(|(pred, span)| pred.has_non_region_bound_vars().then_some(span)) .collect() } diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs index f19cd19c99a..ceffc1d45c5 100644 --- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs +++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs @@ -600,21 +600,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // Check supertraits hold. This is so that their associated type bounds // will be checked in the code below. - for super_trait in tcx + for (supertrait, _) in tcx .explicit_super_predicates_of(trait_predicate.def_id()) - .instantiate(tcx, trait_predicate.trait_ref.args) - .predicates - .into_iter() + .iter_instantiated_copied(tcx, trait_predicate.trait_ref.args) { - let normalized_super_trait = normalize_with_depth_to( + let normalized_supertrait = normalize_with_depth_to( self, obligation.param_env, obligation.cause.clone(), obligation.recursion_depth + 1, - super_trait, + supertrait, &mut nested, ); - nested.push(obligation.with(tcx, normalized_super_trait)); + nested.push(obligation.with(tcx, normalized_supertrait)); } let assoc_types: Vec<_> = tcx diff --git a/compiler/rustc_trait_selection/src/traits/util.rs b/compiler/rustc_trait_selection/src/traits/util.rs index 52f87699b16..279f13896f4 100644 --- a/compiler/rustc_trait_selection/src/traits/util.rs +++ b/compiler/rustc_trait_selection/src/traits/util.rs @@ -131,7 +131,7 @@ impl<'tcx> TraitAliasExpander<'tcx> { let predicates = tcx.explicit_super_predicates_of(trait_ref.def_id()); debug!(?predicates); - let items = predicates.predicates.iter().rev().filter_map(|(pred, span)| { + let items = predicates.skip_binder().iter().rev().filter_map(|(pred, span)| { pred.instantiate_supertrait(tcx, trait_ref) .as_trait_clause() .map(|trait_ref| item.clone_and_push(trait_ref.map_bound(|t| t.trait_ref), *span)) diff --git a/compiler/rustc_trait_selection/src/traits/vtable.rs b/compiler/rustc_trait_selection/src/traits/vtable.rs index 1729d8d307a..fcd7371e2aa 100644 --- a/compiler/rustc_trait_selection/src/traits/vtable.rs +++ b/compiler/rustc_trait_selection/src/traits/vtable.rs @@ -120,8 +120,7 @@ fn prepare_vtable_segments_inner<'tcx, T>( let mut direct_super_traits_iter = tcx .explicit_super_predicates_of(inner_most_trait_ref.def_id()) - .predicates - .into_iter() + .iter_identity_copied() .filter_map(move |(pred, _)| { pred.instantiate_supertrait(tcx, inner_most_trait_ref).as_trait_clause() }); diff --git a/compiler/rustc_type_ir/src/ty_kind.rs b/compiler/rustc_type_ir/src/ty_kind.rs index 328b6739d97..80c3565911e 100644 --- a/compiler/rustc_type_ir/src/ty_kind.rs +++ b/compiler/rustc_type_ir/src/ty_kind.rs @@ -254,13 +254,6 @@ pub enum TyKind<I: Interner> { Error(I::ErrorGuaranteed), } -impl<I: Interner> TyKind<I> { - #[inline] - pub fn is_primitive(&self) -> bool { - matches!(self, Bool | Char | Int(_) | Uint(_) | Float(_)) - } -} - // This is manually implemented because a derive would require `I: Debug` impl<I: Interner> fmt::Debug for TyKind<I> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { diff --git a/library/alloc/benches/lib.rs b/library/alloc/benches/lib.rs index 0561f49c967..ae9608ec7bd 100644 --- a/library/alloc/benches/lib.rs +++ b/library/alloc/benches/lib.rs @@ -1,6 +1,3 @@ -// Disabling on android for the time being -// See https://github.com/rust-lang/rust/issues/73535#event-3477699747 -#![cfg(not(target_os = "android"))] // Disabling in Miri as these would take too long. #![cfg(not(miri))] #![feature(btree_extract_if)] diff --git a/library/alloc/tests/string.rs b/library/alloc/tests/string.rs index c5bc4185a36..dc03c4860e8 100644 --- a/library/alloc/tests/string.rs +++ b/library/alloc/tests/string.rs @@ -723,7 +723,6 @@ fn test_reserve_exact() { #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM -#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_with_capacity() { let string = String::try_with_capacity(1000).unwrap(); assert_eq!(0, string.len()); @@ -734,7 +733,6 @@ fn test_try_with_capacity() { #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM -#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_reserve() { // These are the interesting cases: // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM) @@ -803,7 +801,6 @@ fn test_try_reserve() { #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM -#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_reserve_exact() { // This is exactly the same as test_try_reserve with the method changed. // See that test for comments. diff --git a/library/alloc/tests/vec.rs b/library/alloc/tests/vec.rs index fd2ddbf59e4..3722fb06a6a 100644 --- a/library/alloc/tests/vec.rs +++ b/library/alloc/tests/vec.rs @@ -1695,7 +1695,6 @@ fn test_reserve_exact() { #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM -#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_with_capacity() { let mut vec: Vec<u32> = Vec::try_with_capacity(5).unwrap(); assert_eq!(0, vec.len()); @@ -1707,7 +1706,6 @@ fn test_try_with_capacity() { #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM -#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_reserve() { // These are the interesting cases: // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM) @@ -1803,7 +1801,6 @@ fn test_try_reserve() { #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM -#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_reserve_exact() { // This is exactly the same as test_try_reserve with the method changed. // See that test for comments. diff --git a/library/alloc/tests/vec_deque.rs b/library/alloc/tests/vec_deque.rs index db972122fef..f32ba8d5aa4 100644 --- a/library/alloc/tests/vec_deque.rs +++ b/library/alloc/tests/vec_deque.rs @@ -1185,7 +1185,6 @@ fn test_reserve_exact_2() { #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM -#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_with_capacity() { let vec: VecDeque<u32> = VecDeque::try_with_capacity(5).unwrap(); assert_eq!(0, vec.len()); @@ -1196,7 +1195,6 @@ fn test_try_with_capacity() { #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM -#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_reserve() { // These are the interesting cases: // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM) @@ -1292,7 +1290,6 @@ fn test_try_reserve() { #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM -#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_reserve_exact() { // This is exactly the same as test_try_reserve with the method changed. // See that test for comments. diff --git a/library/backtrace b/library/backtrace -Subproject 72265bea210891ae47bbe6d4f17b493ef060661 +Subproject 230570f2dac80a601f5c0b30da00cc9480bd35e diff --git a/library/core/tests/num/int_log.rs b/library/core/tests/num/int_log.rs index 2320a7acc35..60902752dab 100644 --- a/library/core/tests/num/int_log.rs +++ b/library/core/tests/num/int_log.rs @@ -1,7 +1,4 @@ -//! This tests the `Integer::{ilog,log2,log10}` methods. These tests are in a -//! separate file because there's both a large number of them, and not all tests -//! can be run on Android. This is because in Android `ilog2` uses an imprecise -//! approximation:https://github.com/rust-lang/rust/blob/4825e12fc9c79954aa0fe18f5521efa6c19c7539/src/libstd/sys/unix/android.rs#L27-L53 +//! Tests for the `Integer::{ilog,log2,log10}` methods. #[test] fn checked_ilog() { @@ -48,6 +45,10 @@ fn checked_ilog2() { assert_eq!(0i8.checked_ilog2(), None); assert_eq!(0i16.checked_ilog2(), None); + assert_eq!(8192u16.checked_ilog2(), Some((8192f32).log2() as u32)); + assert_eq!(32768u16.checked_ilog2(), Some((32768f32).log2() as u32)); + assert_eq!(8192i16.checked_ilog2(), Some((8192f32).log2() as u32)); + for i in 1..=u8::MAX { assert_eq!(i.checked_ilog2(), Some((i as f32).log2() as u32), "checking {i}"); } @@ -77,15 +78,6 @@ fn checked_ilog2() { } } -// Validate cases that fail on Android's imprecise float ilog2 implementation. -#[test] -#[cfg(not(target_os = "android"))] -fn checked_ilog2_not_android() { - assert_eq!(8192u16.checked_ilog2(), Some((8192f32).log2() as u32)); - assert_eq!(32768u16.checked_ilog2(), Some((32768f32).log2() as u32)); - assert_eq!(8192i16.checked_ilog2(), Some((8192f32).log2() as u32)); -} - #[test] fn checked_ilog10() { assert_eq!(0u8.checked_ilog10(), None); diff --git a/library/std/src/io/buffered/bufreader.rs b/library/std/src/io/buffered/bufreader.rs index 0b12e5777c8..cf226bd28d0 100644 --- a/library/std/src/io/buffered/bufreader.rs +++ b/library/std/src/io/buffered/bufreader.rs @@ -94,7 +94,9 @@ impl<R: Read> BufReader<R> { pub fn with_capacity(capacity: usize, inner: R) -> BufReader<R> { BufReader { inner, buf: Buffer::with_capacity(capacity) } } +} +impl<R: Read + ?Sized> BufReader<R> { /// Attempt to look ahead `n` bytes. /// /// `n` must be less than `capacity`. diff --git a/library/std/src/sys/pal/wasi/thread.rs b/library/std/src/sys/pal/wasi/thread.rs index 31c9cbd4699..4b83870fdea 100644 --- a/library/std/src/sys/pal/wasi/thread.rs +++ b/library/std/src/sys/pal/wasi/thread.rs @@ -136,36 +136,37 @@ impl Thread { } pub fn sleep(dur: Duration) { - let nanos = dur.as_nanos(); - assert!(nanos <= u64::MAX as u128); - - const USERDATA: wasi::Userdata = 0x0123_45678; - - let clock = wasi::SubscriptionClock { - id: wasi::CLOCKID_MONOTONIC, - timeout: nanos as u64, - precision: 0, - flags: 0, - }; - - let in_ = wasi::Subscription { - userdata: USERDATA, - u: wasi::SubscriptionU { tag: 0, u: wasi::SubscriptionUU { clock } }, - }; - unsafe { - let mut event: wasi::Event = mem::zeroed(); - let res = wasi::poll_oneoff(&in_, &mut event, 1); - match (res, event) { - ( - Ok(1), - wasi::Event { - userdata: USERDATA, - error: wasi::ERRNO_SUCCESS, - type_: wasi::EVENTTYPE_CLOCK, - .. - }, - ) => {} - _ => panic!("thread::sleep(): unexpected result of poll_oneoff"), + let mut nanos = dur.as_nanos(); + while nanos > 0 { + const USERDATA: wasi::Userdata = 0x0123_45678; + + let clock = wasi::SubscriptionClock { + id: wasi::CLOCKID_MONOTONIC, + timeout: u64::try_from(nanos).unwrap_or(u64::MAX), + precision: 0, + flags: 0, + }; + nanos -= u128::from(clock.timeout); + + let in_ = wasi::Subscription { + userdata: USERDATA, + u: wasi::SubscriptionU { tag: 0, u: wasi::SubscriptionUU { clock } }, + }; + unsafe { + let mut event: wasi::Event = mem::zeroed(); + let res = wasi::poll_oneoff(&in_, &mut event, 1); + match (res, event) { + ( + Ok(1), + wasi::Event { + userdata: USERDATA, + error: wasi::ERRNO_SUCCESS, + type_: wasi::EVENTTYPE_CLOCK, + .. + }, + ) => {} + _ => panic!("thread::sleep(): unexpected result of poll_oneoff"), + } } } } diff --git a/src/bootstrap/src/core/build_steps/test.rs b/src/bootstrap/src/core/build_steps/test.rs index cc01afd4c18..84a6b26a491 100644 --- a/src/bootstrap/src/core/build_steps/test.rs +++ b/src/bootstrap/src/core/build_steps/test.rs @@ -14,9 +14,8 @@ use crate::core::build_steps::synthetic_targets::MirOptPanicAbortSyntheticTarget use crate::core::build_steps::tool::{self, SourceType, Tool}; use crate::core::build_steps::toolstate::ToolState; use crate::core::build_steps::{compile, dist, llvm}; -use crate::core::builder; use crate::core::builder::{ - crate_description, Builder, Compiler, Kind, RunConfig, ShouldRun, Step, + self, crate_description, Alias, Builder, Compiler, Kind, RunConfig, ShouldRun, Step, }; use crate::core::config::flags::{get_completion, Subcommand}; use crate::core::config::TargetSelection; @@ -2435,18 +2434,14 @@ impl Step for CrateLibrustc { const ONLY_HOSTS: bool = true; fn should_run(run: ShouldRun<'_>) -> ShouldRun<'_> { - run.crate_or_deps("rustc-main") + run.crate_or_deps("rustc-main").path("compiler") } fn make_run(run: RunConfig<'_>) { let builder = run.builder; let host = run.build_triple(); let compiler = builder.compiler_for(builder.top_stage, host, host); - let crates = run - .paths - .iter() - .map(|p| builder.crate_paths[&p.assert_single_path().path].clone()) - .collect(); + let crates = run.make_run_crates(Alias::Compiler); builder.ensure(CrateLibrustc { compiler, target: run.target, crates }); } diff --git a/src/doc/rustc/src/command-line-arguments.md b/src/doc/rustc/src/command-line-arguments.md index fa23e3e414d..e5631ba4274 100644 --- a/src/doc/rustc/src/command-line-arguments.md +++ b/src/doc/rustc/src/command-line-arguments.md @@ -47,7 +47,7 @@ KIND=PATH` where `KIND` may be one of: directory. - `native` — Only search for native libraries in this directory. - `framework` — Only search for macOS frameworks in this directory. -- `all` — Search for all library kinds in this directory. This is the default +- `all` — Search for all library kinds in this directory, except frameworks. This is the default if `KIND` is not specified. <a id="option-l-link-lib"></a> diff --git a/src/librustdoc/clean/simplify.rs b/src/librustdoc/clean/simplify.rs index b59f939025e..b8db82e540c 100644 --- a/src/librustdoc/clean/simplify.rs +++ b/src/librustdoc/clean/simplify.rs @@ -14,7 +14,6 @@ use rustc_data_structures::fx::FxIndexMap; use rustc_data_structures::unord::UnordSet; use rustc_hir::def_id::DefId; -use rustc_middle::ty; use thin_vec::ThinVec; use crate::clean; @@ -113,18 +112,9 @@ fn trait_is_same_or_supertrait(cx: &DocContext<'_>, child: DefId, trait_: DefId) return true; } let predicates = cx.tcx.explicit_super_predicates_of(child); - debug_assert!(cx.tcx.generics_of(child).has_self); - let self_ty = cx.tcx.types.self_param; predicates - .predicates - .iter() - .filter_map(|(pred, _)| { - if let ty::ClauseKind::Trait(pred) = pred.kind().skip_binder() { - if pred.trait_ref.self_ty() == self_ty { Some(pred.def_id()) } else { None } - } else { - None - } - }) + .iter_identity_copied() + .filter_map(|(pred, _)| Some(pred.as_trait_clause()?.def_id())) .any(|did| trait_is_same_or_supertrait(cx, did, trait_)) } diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js index be0ec425946..6f575e60ed4 100644 --- a/src/librustdoc/html/static/js/search.js +++ b/src/librustdoc/html/static/js/search.js @@ -16,6 +16,7 @@ if (!Array.prototype.toSpliced) { } (function() { +// ==================== Core search logic begin ==================== // This mapping table should match the discriminants of // `rustdoc::formats::item_type::ItemType` type in Rust. const itemTypes = [ @@ -48,35 +49,6 @@ const itemTypes = [ "generic", ]; -const longItemTypes = [ - "keyword", - "primitive type", - "module", - "extern crate", - "re-export", - "struct", - "enum", - "function", - "type alias", - "static", - "trait", - "", - "trait method", - "method", - "struct field", - "enum variant", - "macro", - "assoc type", - "constant", - "assoc const", - "union", - "foreign type", - "existential type", - "attribute macro", - "derive macro", - "trait alias", -]; - // used for special search precedence const TY_GENERIC = itemTypes.indexOf("generic"); const TY_IMPORT = itemTypes.indexOf("import"); @@ -93,44 +65,8 @@ const UNBOXING_LIMIT = 5; const REGEX_IDENT = /\p{ID_Start}\p{ID_Continue}*|_\p{ID_Continue}+/uy; const REGEX_INVALID_TYPE_FILTER = /[^a-z]/ui; -// In the search display, allows to switch between tabs. -function printTab(nb) { - let iter = 0; - let foundCurrentTab = false; - let foundCurrentResultSet = false; - onEachLazy(document.getElementById("search-tabs").childNodes, elem => { - if (nb === iter) { - addClass(elem, "selected"); - foundCurrentTab = true; - } else { - removeClass(elem, "selected"); - } - iter += 1; - }); - const isTypeSearch = (nb > 0 || iter === 1); - iter = 0; - onEachLazy(document.getElementById("results").childNodes, elem => { - if (nb === iter) { - addClass(elem, "active"); - foundCurrentResultSet = true; - } else { - removeClass(elem, "active"); - } - iter += 1; - }); - if (foundCurrentTab && foundCurrentResultSet) { - searchState.currentTab = nb; - // Corrections only kick in on type-based searches. - const correctionsElem = document.getElementsByClassName("search-corrections"); - if (isTypeSearch) { - removeClass(correctionsElem[0], "hidden"); - } else { - addClass(correctionsElem[0], "hidden"); - } - } else if (nb !== 0) { - printTab(0); - } -} +const MAX_RESULTS = 200; +const NO_TYPE_FILTER = -1; /** * The [edit distance] is a metric for measuring the difference between two strings. @@ -240,1001 +176,1564 @@ function editDistance(a, b, limit) { return editDistanceState.calculate(a, b, limit); } -function initSearch(rawSearchIndex) { - const MAX_RESULTS = 200; - const NO_TYPE_FILTER = -1; - /** - * @type {Array<Row>} - */ - let searchIndex; - /** - * @type {Map<String, RoaringBitmap>} - */ - let searchIndexDeprecated; - /** - * @type {Map<String, RoaringBitmap>} - */ - let searchIndexEmptyDesc; - /** - * @type {Uint32Array} - */ - let functionTypeFingerprint; - let currentResults; - /** - * Map from normalized type names to integers. Used to make type search - * more efficient. - * - * @type {Map<string, {id: integer, assocOnly: boolean}>} - */ - const typeNameIdMap = new Map(); - const ALIASES = new Map(); - - /** - * Special type name IDs for searching by array. - */ - const typeNameIdOfArray = buildTypeMapIndex("array"); - /** - * Special type name IDs for searching by slice. - */ - const typeNameIdOfSlice = buildTypeMapIndex("slice"); - /** - * Special type name IDs for searching by both array and slice (`[]` syntax). - */ - const typeNameIdOfArrayOrSlice = buildTypeMapIndex("[]"); - /** - * Special type name IDs for searching by tuple. - */ - const typeNameIdOfTuple = buildTypeMapIndex("tuple"); - /** - * Special type name IDs for searching by unit. - */ - const typeNameIdOfUnit = buildTypeMapIndex("unit"); - /** - * Special type name IDs for searching by both tuple and unit (`()` syntax). - */ - const typeNameIdOfTupleOrUnit = buildTypeMapIndex("()"); - /** - * Special type name IDs for searching `fn`. - */ - const typeNameIdOfFn = buildTypeMapIndex("fn"); - /** - * Special type name IDs for searching `fnmut`. - */ - const typeNameIdOfFnMut = buildTypeMapIndex("fnmut"); - /** - * Special type name IDs for searching `fnonce`. - */ - const typeNameIdOfFnOnce = buildTypeMapIndex("fnonce"); - /** - * Special type name IDs for searching higher order functions (`->` syntax). - */ - const typeNameIdOfHof = buildTypeMapIndex("->"); - - /** - * Add an item to the type Name->ID map, or, if one already exists, use it. - * Returns the number. If name is "" or null, return null (pure generic). - * - * This is effectively string interning, so that function matching can be - * done more quickly. Two types with the same name but different item kinds - * get the same ID. - * - * @param {string} name - * @param {boolean} isAssocType - True if this is an assoc type - * - * @returns {integer} - */ - function buildTypeMapIndex(name, isAssocType) { - if (name === "" || name === null) { - return null; - } - - if (typeNameIdMap.has(name)) { - const obj = typeNameIdMap.get(name); - obj.assocOnly = isAssocType && obj.assocOnly; - return obj.id; - } else { - const id = typeNameIdMap.size; - typeNameIdMap.set(name, {id, assocOnly: isAssocType}); - return id; - } - } - - function isSpecialStartCharacter(c) { - return "<\"".indexOf(c) !== -1; - } +function isEndCharacter(c) { + return "=,>-])".indexOf(c) !== -1; +} - function isEndCharacter(c) { - return "=,>-])".indexOf(c) !== -1; - } +/** + * Returns `true` if the given `c` character is a separator. + * + * @param {string} c + * + * @return {boolean} + */ +function isSeparatorCharacter(c) { + return c === "," || c === "="; +} - function itemTypeFromName(typename) { - const index = itemTypes.findIndex(i => i === typename); - if (index < 0) { - throw ["Unknown type filter ", typename]; - } - return index; - } +/** + * Returns `true` if the current parser position is starting with "->". + * + * @param {ParserState} parserState + * + * @return {boolean} + */ +function isReturnArrow(parserState) { + return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) === "->"; +} - /** - * If we encounter a `"`, then we try to extract the string from it until we find another `"`. - * - * This function will throw an error in the following cases: - * * There is already another string element. - * * We are parsing a generic argument. - * * There is more than one element. - * * There is no closing `"`. - * - * @param {ParsedQuery} query - * @param {ParserState} parserState - * @param {boolean} isInGenerics - */ - function getStringElem(query, parserState, isInGenerics) { - if (isInGenerics) { - throw ["Unexpected ", "\"", " in generics"]; - } else if (query.literalSearch) { - throw ["Cannot have more than one literal search element"]; - } else if (parserState.totalElems - parserState.genericsElems > 0) { - throw ["Cannot use literal search when there is more than one element"]; +/** + * Increase current parser position until it doesn't find a whitespace anymore. + * + * @param {ParserState} parserState + */ +function skipWhitespace(parserState) { + while (parserState.pos < parserState.userQuery.length) { + const c = parserState.userQuery[parserState.pos]; + if (c !== " ") { + break; } parserState.pos += 1; - const start = parserState.pos; - const end = getIdentEndPosition(parserState); - if (parserState.pos >= parserState.length) { - throw ["Unclosed ", "\""]; - } else if (parserState.userQuery[end] !== "\"") { - throw ["Unexpected ", parserState.userQuery[end], " in a string element"]; - } else if (start === end) { - throw ["Cannot have empty string element"]; - } - // To skip the quote at the end. - parserState.pos += 1; - query.literalSearch = true; - } - - /** - * Returns `true` if the current parser position is starting with "::". - * - * @param {ParserState} parserState - * - * @return {boolean} - */ - function isPathStart(parserState) { - return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) === "::"; - } - - /** - * Returns `true` if the current parser position is starting with "->". - * - * @param {ParserState} parserState - * - * @return {boolean} - */ - function isReturnArrow(parserState) { - return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) === "->"; } +} - /** - * If the current parser position is at the beginning of an identifier, - * move the position to the end of it and return `true`. Otherwise, return `false`. - * - * @param {ParserState} parserState - * - * @return {boolean} - */ - function consumeIdent(parserState) { - REGEX_IDENT.lastIndex = parserState.pos; - const match = parserState.userQuery.match(REGEX_IDENT); - if (match) { - parserState.pos += match[0].length; +/** + * Returns `true` if the previous character is `lookingFor`. + * + * @param {ParserState} parserState + * @param {String} lookingFor + * + * @return {boolean} + */ +function prevIs(parserState, lookingFor) { + let pos = parserState.pos; + while (pos > 0) { + const c = parserState.userQuery[pos - 1]; + if (c === lookingFor) { return true; + } else if (c !== " ") { + break; } - return false; + pos -= 1; } + return false; +} - /** - * Returns `true` if the given `c` character is a separator. - * - * @param {string} c - * - * @return {boolean} - */ - function isSeparatorCharacter(c) { - return c === "," || c === "="; - } +/** + * Returns `true` if the last element in the `elems` argument has generics. + * + * @param {Array<QueryElement>} elems + * @param {ParserState} parserState + * + * @return {boolean} + */ +function isLastElemGeneric(elems, parserState) { + return (elems.length > 0 && elems[elems.length - 1].generics.length > 0) || + prevIs(parserState, ">"); +} - /** - * Returns `true` if the given `c` character is a path separator. For example - * `:` in `a::b` or a whitespace in `a b`. - * - * @param {string} c - * - * @return {boolean} - */ - function isPathSeparator(c) { - return c === ":" || c === " "; +function getFilteredNextElem(query, parserState, elems, isInGenerics) { + const start = parserState.pos; + if (parserState.userQuery[parserState.pos] === ":" && !isPathStart(parserState)) { + throw ["Expected type filter before ", ":"]; } - - /** - * Returns `true` if the previous character is `lookingFor`. - * - * @param {ParserState} parserState - * @param {String} lookingFor - * - * @return {boolean} - */ - function prevIs(parserState, lookingFor) { - let pos = parserState.pos; - while (pos > 0) { - const c = parserState.userQuery[pos - 1]; - if (c === lookingFor) { - return true; - } else if (c !== " ") { - break; - } - pos -= 1; + getNextElem(query, parserState, elems, isInGenerics); + if (parserState.userQuery[parserState.pos] === ":" && !isPathStart(parserState)) { + if (parserState.typeFilter !== null) { + throw [ + "Unexpected ", + ":", + " (expected path after type filter ", + parserState.typeFilter + ":", + ")", + ]; } - return false; + if (elems.length === 0) { + throw ["Expected type filter before ", ":"]; + } else if (query.literalSearch) { + throw ["Cannot use quotes on type filter"]; + } + // The type filter doesn't count as an element since it's a modifier. + const typeFilterElem = elems.pop(); + checkExtraTypeFilterCharacters(start, parserState); + parserState.typeFilter = typeFilterElem.name; + parserState.pos += 1; + parserState.totalElems -= 1; + query.literalSearch = false; + getNextElem(query, parserState, elems, isInGenerics); } +} - /** - * Returns `true` if the last element in the `elems` argument has generics. - * - * @param {Array<QueryElement>} elems - * @param {ParserState} parserState - * - * @return {boolean} - */ - function isLastElemGeneric(elems, parserState) { - return (elems.length > 0 && elems[elems.length - 1].generics.length > 0) || - prevIs(parserState, ">"); +/** + * This function parses the next query element until it finds `endChar`, + * calling `getNextElem` to collect each element. + * + * If there is no `endChar`, this function will implicitly stop at the end + * without raising an error. + * + * @param {ParsedQuery} query + * @param {ParserState} parserState + * @param {Array<QueryElement>} elems - This is where the new {QueryElement} will be added. + * @param {string} endChar - This function will stop when it'll encounter this + * character. + * @returns {{foundSeparator: bool}} + */ +function getItemsBefore(query, parserState, elems, endChar) { + let foundStopChar = true; + let foundSeparator = false; + + // If this is a generic, keep the outer item's type filter around. + const oldTypeFilter = parserState.typeFilter; + parserState.typeFilter = null; + const oldIsInBinding = parserState.isInBinding; + parserState.isInBinding = null; + + // ML-style Higher Order Function notation + // + // a way to search for any closure or fn pointer regardless of + // which closure trait is used + // + // Looks like this: + // + // `option<t>, (t -> u) -> option<u>` + // ^^^^^^ + // + // The Rust-style closure notation is implemented in getNextElem + let hofParameters = null; + + let extra = ""; + if (endChar === ">") { + extra = "<"; + } else if (endChar === "]") { + extra = "["; + } else if (endChar === ")") { + extra = "("; + } else if (endChar === "") { + extra = "->"; + } else { + extra = endChar; } - /** - * Increase current parser position until it doesn't find a whitespace anymore. - * - * @param {ParserState} parserState - */ - function skipWhitespace(parserState) { - while (parserState.pos < parserState.userQuery.length) { - const c = parserState.userQuery[parserState.pos]; - if (c !== " ") { - break; + while (parserState.pos < parserState.length) { + const c = parserState.userQuery[parserState.pos]; + if (c === endChar) { + if (parserState.isInBinding) { + throw ["Unexpected ", endChar, " after ", "="]; + } + break; + } else if (endChar !== "" && isReturnArrow(parserState)) { + // ML-style HOF notation only works when delimited in something, + // otherwise a function arrow starts the return type of the top + if (parserState.isInBinding) { + throw ["Unexpected ", "->", " after ", "="]; } + hofParameters = [...elems]; + elems.length = 0; + parserState.pos += 2; + foundStopChar = true; + foundSeparator = false; + continue; + } else if (c === " ") { + parserState.pos += 1; + continue; + } else if (isSeparatorCharacter(c)) { parserState.pos += 1; + foundStopChar = true; + foundSeparator = true; + continue; + } else if (c === ":" && isPathStart(parserState)) { + throw ["Unexpected ", "::", ": paths cannot start with ", "::"]; + } else if (isEndCharacter(c)) { + throw ["Unexpected ", c, " after ", extra]; + } + if (!foundStopChar) { + let extra = []; + if (isLastElemGeneric(query.elems, parserState)) { + extra = [" after ", ">"]; + } else if (prevIs(parserState, "\"")) { + throw ["Cannot have more than one element if you use quotes"]; + } + if (endChar !== "") { + throw [ + "Expected ", + ",", + ", ", + "=", + ", or ", + endChar, + ...extra, + ", found ", + c, + ]; + } + throw [ + "Expected ", + ",", + " or ", + "=", + ...extra, + ", found ", + c, + ]; } + const posBefore = parserState.pos; + getFilteredNextElem(query, parserState, elems, endChar !== ""); + if (endChar !== "" && parserState.pos >= parserState.length) { + throw ["Unclosed ", extra]; + } + // This case can be encountered if `getNextElem` encountered a "stop character" + // right from the start. For example if you have `,,` or `<>`. In this case, + // we simply move up the current position to continue the parsing. + if (posBefore === parserState.pos) { + parserState.pos += 1; + } + foundStopChar = false; } - - function makePrimitiveElement(name, extra) { - return Object.assign({ - name, - id: null, - fullPath: [name], - pathWithoutLast: [], - pathLast: name, - normalizedPathLast: name, - generics: [], - bindings: new Map(), - typeFilter: "primitive", - bindingName: null, - }, extra); + if (parserState.pos >= parserState.length && endChar !== "") { + throw ["Unclosed ", extra]; + } + // We are either at the end of the string or on the `endChar` character, let's move + // forward in any case. + parserState.pos += 1; + + if (hofParameters) { + // Commas in a HOF don't cause wrapping parens to become a tuple. + // If you want a one-tuple with a HOF in it, write `((a -> b),)`. + foundSeparator = false; + // HOFs can't have directly nested bindings. + if ([...elems, ...hofParameters].some(x => x.bindingName) + || parserState.isInBinding) { + throw ["Unexpected ", "=", " within ", "->"]; + } + // HOFs are represented the same way closures are. + // The arguments are wrapped in a tuple, and the output + // is a binding, even though the compiler doesn't technically + // represent fn pointers that way. + const hofElem = makePrimitiveElement("->", { + generics: hofParameters, + bindings: new Map([["output", [...elems]]]), + typeFilter: null, + }); + elems.length = 0; + elems[0] = hofElem; } - /** - * @param {ParsedQuery} query - * @param {ParserState} parserState - * @param {string} name - Name of the query element. - * @param {Array<QueryElement>} generics - List of generics of this query element. - * - * @return {QueryElement} - The newly created `QueryElement`. - */ - function createQueryElement(query, parserState, name, generics, isInGenerics) { - const path = name.trim(); - if (path.length === 0 && generics.length === 0) { - throw ["Unexpected ", parserState.userQuery[parserState.pos]]; - } - if (query.literalSearch && parserState.totalElems - parserState.genericsElems > 0) { - throw ["Cannot have more than one element if you use quotes"]; + parserState.typeFilter = oldTypeFilter; + parserState.isInBinding = oldIsInBinding; + + return { foundSeparator }; +} + +/** + * @param {ParsedQuery} query + * @param {ParserState} parserState + * @param {Array<QueryElement>} elems - This is where the new {QueryElement} will be added. + * @param {boolean} isInGenerics + */ +function getNextElem(query, parserState, elems, isInGenerics) { + const generics = []; + + skipWhitespace(parserState); + let start = parserState.pos; + let end; + if ("[(".indexOf(parserState.userQuery[parserState.pos]) !== -1) { + let endChar = ")"; + let name = "()"; + let friendlyName = "tuple"; + + if (parserState.userQuery[parserState.pos] === "[") { + endChar = "]"; + name = "[]"; + friendlyName = "slice"; } + parserState.pos += 1; + const { foundSeparator } = getItemsBefore(query, parserState, generics, endChar); const typeFilter = parserState.typeFilter; + const bindingName = parserState.isInBinding; parserState.typeFilter = null; - if (name === "!") { + parserState.isInBinding = null; + for (const gen of generics) { + if (gen.bindingName !== null) { + throw ["Type parameter ", "=", ` cannot be within ${friendlyName} `, name]; + } + } + if (name === "()" && !foundSeparator && generics.length === 1 + && typeFilter === null) { + elems.push(generics[0]); + } else if (name === "()" && generics.length === 1 && generics[0].name === "->") { + // `primitive:(a -> b)` parser to `primitive:"->"<output=b, (a,)>` + // not `primitive:"()"<"->"<output=b, (a,)>>` + generics[0].typeFilter = typeFilter; + elems.push(generics[0]); + } else { if (typeFilter !== null && typeFilter !== "primitive") { throw [ - "Invalid search type: primitive never type ", - "!", + "Invalid search type: primitive ", + name, " and ", typeFilter, " both specified", ]; } - if (generics.length !== 0) { - throw [ - "Never type ", - "!", - " does not accept generic parameters", - ]; - } - const bindingName = parserState.isInBinding; - parserState.isInBinding = null; - return makePrimitiveElement("never", { bindingName }); - } - const quadcolon = /::\s*::/.exec(path); - if (path.startsWith("::")) { - throw ["Paths cannot start with ", "::"]; - } else if (path.endsWith("::")) { - throw ["Paths cannot end with ", "::"]; - } else if (quadcolon !== null) { - throw ["Unexpected ", quadcolon[0]]; - } - const pathSegments = path.split(/(?:::\s*)|(?:\s+(?:::\s*)?)/); - // In case we only have something like `<p>`, there is no name. - if (pathSegments.length === 0 || (pathSegments.length === 1 && pathSegments[0] === "")) { - if (generics.length > 0 || prevIs(parserState, ">")) { - throw ["Found generics without a path"]; - } else { - throw ["Unexpected ", parserState.userQuery[parserState.pos]]; + parserState.totalElems += 1; + if (isInGenerics) { + parserState.genericsElems += 1; } + elems.push(makePrimitiveElement(name, { bindingName, generics })); } - for (const [i, pathSegment] of pathSegments.entries()) { - if (pathSegment === "!") { - if (i !== 0) { - throw ["Never type ", "!", " is not associated item"]; - } - pathSegments[i] = "never"; - } - } - parserState.totalElems += 1; - if (isInGenerics) { - parserState.genericsElems += 1; + } else if (parserState.userQuery[parserState.pos] === "&") { + if (parserState.typeFilter !== null && parserState.typeFilter !== "primitive") { + throw [ + "Invalid search type: primitive ", + "&", + " and ", + parserState.typeFilter, + " both specified", + ]; } - const bindingName = parserState.isInBinding; - parserState.isInBinding = null; - const bindings = new Map(); - const pathLast = pathSegments[pathSegments.length - 1]; - return { - name: name.trim(), - id: null, - fullPath: pathSegments, - pathWithoutLast: pathSegments.slice(0, pathSegments.length - 1), - pathLast, - normalizedPathLast: pathLast.replace(/_/g, ""), - generics: generics.filter(gen => { - // Syntactically, bindings are parsed as generics, - // but the query engine treats them differently. - if (gen.bindingName !== null) { - if (gen.name !== null) { - gen.bindingName.generics.unshift(gen); - } - bindings.set(gen.bindingName.name, gen.bindingName.generics); - return false; - } - return true; - }), - bindings, - typeFilter, - bindingName, - }; - } - - /** - * This function goes through all characters until it reaches an invalid ident character or the - * end of the query. It returns the position of the last character of the ident. - * - * @param {ParserState} parserState - * - * @return {integer} - */ - function getIdentEndPosition(parserState) { - let afterIdent = consumeIdent(parserState); - let end = parserState.pos; - let macroExclamation = -1; - while (parserState.pos < parserState.length) { - const c = parserState.userQuery[parserState.pos]; - if (c === "!") { - if (macroExclamation !== -1) { - throw ["Cannot have more than one ", "!", " in an ident"]; - } else if (parserState.pos + 1 < parserState.length) { - const pos = parserState.pos; - parserState.pos++; - const beforeIdent = consumeIdent(parserState); - parserState.pos = pos; - if (beforeIdent) { - throw ["Unexpected ", "!", ": it can only be at the end of an ident"]; - } - } - if (afterIdent) macroExclamation = parserState.pos; - } else if (isPathSeparator(c)) { - if (c === ":") { - if (!isPathStart(parserState)) { - break; - } - // Skip current ":". - parserState.pos += 1; - } else { - while (parserState.pos + 1 < parserState.length) { - const next_c = parserState.userQuery[parserState.pos + 1]; - if (next_c !== " ") { - break; - } - parserState.pos += 1; - } - } - if (macroExclamation !== -1) { - throw ["Cannot have associated items in macros"]; - } - } else if ( - c === "[" || - c === "(" || - isEndCharacter(c) || - isSpecialStartCharacter(c) || - isSeparatorCharacter(c) - ) { - break; - } else if (parserState.pos > 0) { - throw ["Unexpected ", c, " after ", parserState.userQuery[parserState.pos - 1], - " (not a valid identifier)"]; - } else { - throw ["Unexpected ", c, " (not a valid identifier)"]; - } + parserState.typeFilter = null; + parserState.pos += 1; + let c = parserState.userQuery[parserState.pos]; + while (c === " " && parserState.pos < parserState.length) { parserState.pos += 1; - afterIdent = consumeIdent(parserState); - end = parserState.pos; + c = parserState.userQuery[parserState.pos]; } - if (macroExclamation !== -1) { - if (parserState.typeFilter === null) { - parserState.typeFilter = "macro"; - } else if (parserState.typeFilter !== "macro") { - throw [ - "Invalid search type: macro ", - "!", - " and ", - parserState.typeFilter, - " both specified", - ]; - } - end = macroExclamation; + const generics = []; + if (parserState.userQuery.slice(parserState.pos, parserState.pos + 3) === "mut") { + generics.push(makePrimitiveElement("mut", { typeFilter: "keyword" })); + parserState.pos += 3; + c = parserState.userQuery[parserState.pos]; } - return end; - } - - function getFilteredNextElem(query, parserState, elems, isInGenerics) { - const start = parserState.pos; - if (parserState.userQuery[parserState.pos] === ":" && !isPathStart(parserState)) { - throw ["Expected type filter before ", ":"]; + while (c === " " && parserState.pos < parserState.length) { + parserState.pos += 1; + c = parserState.userQuery[parserState.pos]; + } + if (!isEndCharacter(c) && parserState.pos < parserState.length) { + getFilteredNextElem(query, parserState, generics, isInGenerics); + } + elems.push(makePrimitiveElement("reference", { generics })); + } else { + const isStringElem = parserState.userQuery[start] === "\""; + // We handle the strings on their own mostly to make code easier to follow. + if (isStringElem) { + start += 1; + getStringElem(query, parserState, isInGenerics); + end = parserState.pos - 1; + } else { + end = getIdentEndPosition(parserState); } - getNextElem(query, parserState, elems, isInGenerics); - if (parserState.userQuery[parserState.pos] === ":" && !isPathStart(parserState)) { - if (parserState.typeFilter !== null) { - throw [ - "Unexpected ", - ":", - " (expected path after type filter ", - parserState.typeFilter + ":", - ")", - ]; - } - if (elems.length === 0) { - throw ["Expected type filter before ", ":"]; - } else if (query.literalSearch) { - throw ["Cannot use quotes on type filter"]; + if (parserState.pos < parserState.length && + parserState.userQuery[parserState.pos] === "<" + ) { + if (start >= end) { + throw ["Found generics without a path"]; } - // The type filter doesn't count as an element since it's a modifier. - const typeFilterElem = elems.pop(); - checkExtraTypeFilterCharacters(start, parserState); - parserState.typeFilter = typeFilterElem.name; parserState.pos += 1; - parserState.totalElems -= 1; - query.literalSearch = false; - getNextElem(query, parserState, elems, isInGenerics); - } - } - - /** - * @param {ParsedQuery} query - * @param {ParserState} parserState - * @param {Array<QueryElement>} elems - This is where the new {QueryElement} will be added. - * @param {boolean} isInGenerics - */ - function getNextElem(query, parserState, elems, isInGenerics) { - const generics = []; - - skipWhitespace(parserState); - let start = parserState.pos; - let end; - if ("[(".indexOf(parserState.userQuery[parserState.pos]) !== -1) { - let endChar = ")"; - let name = "()"; - let friendlyName = "tuple"; - - if (parserState.userQuery[parserState.pos] === "[") { - endChar = "]"; - name = "[]"; - friendlyName = "slice"; + getItemsBefore(query, parserState, generics, ">"); + } else if (parserState.pos < parserState.length && + parserState.userQuery[parserState.pos] === "(" + ) { + if (start >= end) { + throw ["Found generics without a path"]; + } + if (parserState.isInBinding) { + throw ["Unexpected ", "(", " after ", "="]; } parserState.pos += 1; - const { foundSeparator } = getItemsBefore(query, parserState, generics, endChar); const typeFilter = parserState.typeFilter; - const bindingName = parserState.isInBinding; parserState.typeFilter = null; - parserState.isInBinding = null; - for (const gen of generics) { - if (gen.bindingName !== null) { - throw ["Type parameter ", "=", ` cannot be within ${friendlyName} `, name]; - } - } - if (name === "()" && !foundSeparator && generics.length === 1 && typeFilter === null) { - elems.push(generics[0]); - } else if (name === "()" && generics.length === 1 && generics[0].name === "->") { - // `primitive:(a -> b)` parser to `primitive:"->"<output=b, (a,)>` - // not `primitive:"()"<"->"<output=b, (a,)>>` - generics[0].typeFilter = typeFilter; - elems.push(generics[0]); + getItemsBefore(query, parserState, generics, ")"); + skipWhitespace(parserState); + if (isReturnArrow(parserState)) { + parserState.pos += 2; + skipWhitespace(parserState); + getFilteredNextElem(query, parserState, generics, isInGenerics); + generics[generics.length - 1].bindingName = makePrimitiveElement("output"); } else { - if (typeFilter !== null && typeFilter !== "primitive") { - throw [ - "Invalid search type: primitive ", - name, - " and ", - typeFilter, - " both specified", - ]; - } - parserState.totalElems += 1; - if (isInGenerics) { - parserState.genericsElems += 1; - } - elems.push(makePrimitiveElement(name, { bindingName, generics })); + generics.push(makePrimitiveElement(null, { + bindingName: makePrimitiveElement("output"), + typeFilter: null, + })); } - } else if (parserState.userQuery[parserState.pos] === "&") { - if (parserState.typeFilter !== null && parserState.typeFilter !== "primitive") { - throw [ - "Invalid search type: primitive ", - "&", - " and ", - parserState.typeFilter, - " both specified", - ]; + parserState.typeFilter = typeFilter; + } + if (isStringElem) { + skipWhitespace(parserState); + } + if (start >= end && generics.length === 0) { + return; + } + if (parserState.userQuery[parserState.pos] === "=") { + if (parserState.isInBinding) { + throw ["Cannot write ", "=", " twice in a binding"]; } - parserState.typeFilter = null; - parserState.pos += 1; - let c = parserState.userQuery[parserState.pos]; - while (c === " " && parserState.pos < parserState.length) { - parserState.pos += 1; - c = parserState.userQuery[parserState.pos]; + if (!isInGenerics) { + throw ["Type parameter ", "=", " must be within generics list"]; } - const generics = []; - if (parserState.userQuery.slice(parserState.pos, parserState.pos + 3) === "mut") { - generics.push(makePrimitiveElement("mut", { typeFilter: "keyword"})); - parserState.pos += 3; - c = parserState.userQuery[parserState.pos]; + const name = parserState.userQuery.slice(start, end).trim(); + if (name === "!") { + throw ["Type parameter ", "=", " key cannot be ", "!", " never type"]; } - while (c === " " && parserState.pos < parserState.length) { - parserState.pos += 1; - c = parserState.userQuery[parserState.pos]; + if (name.includes("!")) { + throw ["Type parameter ", "=", " key cannot be ", "!", " macro"]; } - if (!isEndCharacter(c) && parserState.pos < parserState.length) { - getFilteredNextElem(query, parserState, generics, isInGenerics); + if (name.includes("::")) { + throw ["Type parameter ", "=", " key cannot contain ", "::", " path"]; } - elems.push(makePrimitiveElement("reference", { generics })); + if (name.includes(":")) { + throw ["Type parameter ", "=", " key cannot contain ", ":", " type"]; + } + parserState.isInBinding = { name, generics }; } else { - const isStringElem = parserState.userQuery[start] === "\""; - // We handle the strings on their own mostly to make code easier to follow. - if (isStringElem) { - start += 1; - getStringElem(query, parserState, isInGenerics); - end = parserState.pos - 1; - } else { - end = getIdentEndPosition(parserState); + elems.push( + createQueryElement( + query, + parserState, + parserState.userQuery.slice(start, end), + generics, + isInGenerics, + ), + ); + } + } +} + +/** + * Checks that the type filter doesn't have unwanted characters like `<>` (which are ignored + * if empty). + * + * @param {ParserState} parserState + */ +function checkExtraTypeFilterCharacters(start, parserState) { + const query = parserState.userQuery.slice(start, parserState.pos).trim(); + + const match = query.match(REGEX_INVALID_TYPE_FILTER); + if (match) { + throw [ + "Unexpected ", + match[0], + " in type filter (before ", + ":", + ")", + ]; + } +} + +/** + * @param {ParsedQuery} query + * @param {ParserState} parserState + * @param {string} name - Name of the query element. + * @param {Array<QueryElement>} generics - List of generics of this query element. + * + * @return {QueryElement} - The newly created `QueryElement`. + */ +function createQueryElement(query, parserState, name, generics, isInGenerics) { + const path = name.trim(); + if (path.length === 0 && generics.length === 0) { + throw ["Unexpected ", parserState.userQuery[parserState.pos]]; + } + if (query.literalSearch && parserState.totalElems - parserState.genericsElems > 0) { + throw ["Cannot have more than one element if you use quotes"]; + } + const typeFilter = parserState.typeFilter; + parserState.typeFilter = null; + if (name === "!") { + if (typeFilter !== null && typeFilter !== "primitive") { + throw [ + "Invalid search type: primitive never type ", + "!", + " and ", + typeFilter, + " both specified", + ]; + } + if (generics.length !== 0) { + throw [ + "Never type ", + "!", + " does not accept generic parameters", + ]; + } + const bindingName = parserState.isInBinding; + parserState.isInBinding = null; + return makePrimitiveElement("never", { bindingName }); + } + const quadcolon = /::\s*::/.exec(path); + if (path.startsWith("::")) { + throw ["Paths cannot start with ", "::"]; + } else if (path.endsWith("::")) { + throw ["Paths cannot end with ", "::"]; + } else if (quadcolon !== null) { + throw ["Unexpected ", quadcolon[0]]; + } + const pathSegments = path.split(/(?:::\s*)|(?:\s+(?:::\s*)?)/); + // In case we only have something like `<p>`, there is no name. + if (pathSegments.length === 0 + || (pathSegments.length === 1 && pathSegments[0] === "")) { + if (generics.length > 0 || prevIs(parserState, ">")) { + throw ["Found generics without a path"]; + } else { + throw ["Unexpected ", parserState.userQuery[parserState.pos]]; + } + } + for (const [i, pathSegment] of pathSegments.entries()) { + if (pathSegment === "!") { + if (i !== 0) { + throw ["Never type ", "!", " is not associated item"]; } - if (parserState.pos < parserState.length && - parserState.userQuery[parserState.pos] === "<" - ) { - if (start >= end) { - throw ["Found generics without a path"]; - } - parserState.pos += 1; - getItemsBefore(query, parserState, generics, ">"); - } else if (parserState.pos < parserState.length && - parserState.userQuery[parserState.pos] === "(" - ) { - if (start >= end) { - throw ["Found generics without a path"]; - } - if (parserState.isInBinding) { - throw ["Unexpected ", "(", " after ", "="]; - } + pathSegments[i] = "never"; + } + } + parserState.totalElems += 1; + if (isInGenerics) { + parserState.genericsElems += 1; + } + const bindingName = parserState.isInBinding; + parserState.isInBinding = null; + const bindings = new Map(); + const pathLast = pathSegments[pathSegments.length - 1]; + return { + name: name.trim(), + id: null, + fullPath: pathSegments, + pathWithoutLast: pathSegments.slice(0, pathSegments.length - 1), + pathLast, + normalizedPathLast: pathLast.replace(/_/g, ""), + generics: generics.filter(gen => { + // Syntactically, bindings are parsed as generics, + // but the query engine treats them differently. + if (gen.bindingName !== null) { + if (gen.name !== null) { + gen.bindingName.generics.unshift(gen); + } + bindings.set(gen.bindingName.name, gen.bindingName.generics); + return false; + } + return true; + }), + bindings, + typeFilter, + bindingName, + }; +} + +function makePrimitiveElement(name, extra) { + return Object.assign({ + name, + id: null, + fullPath: [name], + pathWithoutLast: [], + pathLast: name, + normalizedPathLast: name, + generics: [], + bindings: new Map(), + typeFilter: "primitive", + bindingName: null, + }, extra); +} + +/** + * If we encounter a `"`, then we try to extract the string + * from it until we find another `"`. + * + * This function will throw an error in the following cases: + * * There is already another string element. + * * We are parsing a generic argument. + * * There is more than one element. + * * There is no closing `"`. + * + * @param {ParsedQuery} query + * @param {ParserState} parserState + * @param {boolean} isInGenerics + */ +function getStringElem(query, parserState, isInGenerics) { + if (isInGenerics) { + throw ["Unexpected ", "\"", " in generics"]; + } else if (query.literalSearch) { + throw ["Cannot have more than one literal search element"]; + } else if (parserState.totalElems - parserState.genericsElems > 0) { + throw ["Cannot use literal search when there is more than one element"]; + } + parserState.pos += 1; + const start = parserState.pos; + const end = getIdentEndPosition(parserState); + if (parserState.pos >= parserState.length) { + throw ["Unclosed ", "\""]; + } else if (parserState.userQuery[end] !== "\"") { + throw ["Unexpected ", parserState.userQuery[end], " in a string element"]; + } else if (start === end) { + throw ["Cannot have empty string element"]; + } + // To skip the quote at the end. + parserState.pos += 1; + query.literalSearch = true; +} + +/** + * This function goes through all characters until it reaches an invalid ident + * character or the end of the query. It returns the position of the last + * character of the ident. + * + * @param {ParserState} parserState + * + * @return {integer} + */ +function getIdentEndPosition(parserState) { + let afterIdent = consumeIdent(parserState); + let end = parserState.pos; + let macroExclamation = -1; + while (parserState.pos < parserState.length) { + const c = parserState.userQuery[parserState.pos]; + if (c === "!") { + if (macroExclamation !== -1) { + throw ["Cannot have more than one ", "!", " in an ident"]; + } else if (parserState.pos + 1 < parserState.length) { + const pos = parserState.pos; + parserState.pos++; + const beforeIdent = consumeIdent(parserState); + parserState.pos = pos; + if (beforeIdent) { + throw ["Unexpected ", "!", ": it can only be at the end of an ident"]; + } + } + if (afterIdent) macroExclamation = parserState.pos; + } else if (isPathSeparator(c)) { + if (c === ":") { + if (!isPathStart(parserState)) { + break; + } + // Skip current ":". parserState.pos += 1; - const typeFilter = parserState.typeFilter; - parserState.typeFilter = null; - getItemsBefore(query, parserState, generics, ")"); - skipWhitespace(parserState); - if (isReturnArrow(parserState)) { - parserState.pos += 2; - skipWhitespace(parserState); - getFilteredNextElem(query, parserState, generics, isInGenerics); - generics[generics.length - 1].bindingName = makePrimitiveElement("output"); - } else { - generics.push(makePrimitiveElement(null, { - bindingName: makePrimitiveElement("output"), - typeFilter: null, - })); + } else { + while (parserState.pos + 1 < parserState.length) { + const next_c = parserState.userQuery[parserState.pos + 1]; + if (next_c !== " ") { + break; + } + parserState.pos += 1; } - parserState.typeFilter = typeFilter; - } - if (isStringElem) { - skipWhitespace(parserState); - } - if (start >= end && generics.length === 0) { - return; } - if (parserState.userQuery[parserState.pos] === "=") { - if (parserState.isInBinding) { - throw ["Cannot write ", "=", " twice in a binding"]; - } - if (!isInGenerics) { - throw ["Type parameter ", "=", " must be within generics list"]; - } - const name = parserState.userQuery.slice(start, end).trim(); - if (name === "!") { - throw ["Type parameter ", "=", " key cannot be ", "!", " never type"]; - } - if (name.includes("!")) { - throw ["Type parameter ", "=", " key cannot be ", "!", " macro"]; - } - if (name.includes("::")) { - throw ["Type parameter ", "=", " key cannot contain ", "::", " path"]; - } - if (name.includes(":")) { - throw ["Type parameter ", "=", " key cannot contain ", ":", " type"]; - } - parserState.isInBinding = { name, generics }; - } else { - elems.push( - createQueryElement( - query, - parserState, - parserState.userQuery.slice(start, end), - generics, - isInGenerics, - ), - ); + if (macroExclamation !== -1) { + throw ["Cannot have associated items in macros"]; } + } else if ( + c === "[" || + c === "(" || + isEndCharacter(c) || + isSpecialStartCharacter(c) || + isSeparatorCharacter(c) + ) { + break; + } else if (parserState.pos > 0) { + throw ["Unexpected ", c, " after ", parserState.userQuery[parserState.pos - 1], + " (not a valid identifier)"]; + } else { + throw ["Unexpected ", c, " (not a valid identifier)"]; + } + parserState.pos += 1; + afterIdent = consumeIdent(parserState); + end = parserState.pos; + } + if (macroExclamation !== -1) { + if (parserState.typeFilter === null) { + parserState.typeFilter = "macro"; + } else if (parserState.typeFilter !== "macro") { + throw [ + "Invalid search type: macro ", + "!", + " and ", + parserState.typeFilter, + " both specified", + ]; } + end = macroExclamation; } + return end; +} - /** - * This function parses the next query element until it finds `endChar`, calling `getNextElem` - * to collect each element. - * - * If there is no `endChar`, this function will implicitly stop at the end without raising an - * error. - * - * @param {ParsedQuery} query - * @param {ParserState} parserState - * @param {Array<QueryElement>} elems - This is where the new {QueryElement} will be added. - * @param {string} endChar - This function will stop when it'll encounter this - * character. - * @returns {{foundSeparator: bool}} - */ - function getItemsBefore(query, parserState, elems, endChar) { - let foundStopChar = true; - let foundSeparator = false; +function isSpecialStartCharacter(c) { + return "<\"".indexOf(c) !== -1; +} - // If this is a generic, keep the outer item's type filter around. - const oldTypeFilter = parserState.typeFilter; - parserState.typeFilter = null; - const oldIsInBinding = parserState.isInBinding; - parserState.isInBinding = null; +/** + * Returns `true` if the current parser position is starting with "::". + * + * @param {ParserState} parserState + * + * @return {boolean} + */ +function isPathStart(parserState) { + return parserState.userQuery.slice(parserState.pos, parserState.pos + 2) === "::"; +} - // ML-style Higher Order Function notation - // - // a way to search for any closure or fn pointer regardless of - // which closure trait is used - // - // Looks like this: - // - // `option<t>, (t -> u) -> option<u>` - // ^^^^^^ - // - // The Rust-style closure notation is implemented in getNextElem - let hofParameters = null; - - let extra = ""; - if (endChar === ">") { - extra = "<"; - } else if (endChar === "]") { - extra = "["; - } else if (endChar === ")") { - extra = "("; - } else if (endChar === "") { - extra = "->"; - } else { - extra = endChar; - } +/** + * If the current parser position is at the beginning of an identifier, + * move the position to the end of it and return `true`. Otherwise, return `false`. + * + * @param {ParserState} parserState + * + * @return {boolean} + */ +function consumeIdent(parserState) { + REGEX_IDENT.lastIndex = parserState.pos; + const match = parserState.userQuery.match(REGEX_IDENT); + if (match) { + parserState.pos += match[0].length; + return true; + } + return false; +} - while (parserState.pos < parserState.length) { - const c = parserState.userQuery[parserState.pos]; - if (c === endChar) { - if (parserState.isInBinding) { - throw ["Unexpected ", endChar, " after ", "="]; - } - break; - } else if (endChar !== "" && isReturnArrow(parserState)) { - // ML-style HOF notation only works when delimited in something, - // otherwise a function arrow starts the return type of the top - if (parserState.isInBinding) { - throw ["Unexpected ", "->", " after ", "="]; - } - hofParameters = [...elems]; - elems.length = 0; - parserState.pos += 2; - foundStopChar = true; - foundSeparator = false; - continue; - } else if (c === " ") { - parserState.pos += 1; - continue; - } else if (isSeparatorCharacter(c)) { - parserState.pos += 1; - foundStopChar = true; - foundSeparator = true; - continue; - } else if (c === ":" && isPathStart(parserState)) { - throw ["Unexpected ", "::", ": paths cannot start with ", "::"]; - } else if (isEndCharacter(c)) { - throw ["Unexpected ", c, " after ", extra]; - } - if (!foundStopChar) { - let extra = []; - if (isLastElemGeneric(query.elems, parserState)) { - extra = [" after ", ">"]; - } else if (prevIs(parserState, "\"")) { - throw ["Cannot have more than one element if you use quotes"]; - } - if (endChar !== "") { - throw [ - "Expected ", - ",", - ", ", - "=", - ", or ", - endChar, - ...extra, - ", found ", - c, - ]; - } - throw [ - "Expected ", - ",", - " or ", - "=", - ...extra, - ", found ", - c, - ]; +/** + * Returns `true` if the given `c` character is a path separator. For example + * `:` in `a::b` or a whitespace in `a b`. + * + * @param {string} c + * + * @return {boolean} + */ +function isPathSeparator(c) { + return c === ":" || c === " "; +} + +class VlqHexDecoder { + constructor(string, cons) { + this.string = string; + this.cons = cons; + this.offset = 0; + this.backrefQueue = []; + } + // call after consuming `{` + decodeList() { + let c = this.string.charCodeAt(this.offset); + const ret = []; + while (c !== 125) { // 125 = "}" + ret.push(this.decode()); + c = this.string.charCodeAt(this.offset); + } + this.offset += 1; // eat cb + return ret; + } + // consumes and returns a list or integer + decode() { + let n = 0; + let c = this.string.charCodeAt(this.offset); + if (c === 123) { // 123 = "{" + this.offset += 1; + return this.decodeList(); + } + while (c < 96) { // 96 = "`" + n = (n << 4) | (c & 0xF); + this.offset += 1; + c = this.string.charCodeAt(this.offset); + } + // last character >= la + n = (n << 4) | (c & 0xF); + const [sign, value] = [n & 1, n >> 1]; + this.offset += 1; + return sign ? -value : value; + } + next() { + const c = this.string.charCodeAt(this.offset); + // sixteen characters after "0" are backref + if (c >= 48 && c < 64) { // 48 = "0", 64 = "@" + this.offset += 1; + return this.backrefQueue[c - 48]; + } + // special exception: 0 doesn't use backref encoding + // it's already one character, and it's always nullish + if (c === 96) { // 96 = "`" + this.offset += 1; + return this.cons(0); + } + const result = this.cons(this.decode()); + this.backrefQueue.unshift(result); + if (this.backrefQueue.length > 16) { + this.backrefQueue.pop(); + } + return result; + } +} +class RoaringBitmap { + constructor(str) { + const strdecoded = atob(str); + const u8array = new Uint8Array(strdecoded.length); + for (let j = 0; j < strdecoded.length; ++j) { + u8array[j] = strdecoded.charCodeAt(j); + } + const has_runs = u8array[0] === 0x3b; + const size = has_runs ? + ((u8array[2] | (u8array[3] << 8)) + 1) : + ((u8array[4] | (u8array[5] << 8) | (u8array[6] << 16) | (u8array[7] << 24))); + let i = has_runs ? 4 : 8; + let is_run; + if (has_runs) { + const is_run_len = Math.floor((size + 7) / 8); + is_run = u8array.slice(i, i + is_run_len); + i += is_run_len; + } else { + is_run = new Uint8Array(); + } + this.keys = []; + this.cardinalities = []; + for (let j = 0; j < size; ++j) { + this.keys.push(u8array[i] | (u8array[i + 1] << 8)); + i += 2; + this.cardinalities.push((u8array[i] | (u8array[i + 1] << 8)) + 1); + i += 2; + } + this.containers = []; + let offsets = null; + if (!has_runs || this.keys.length >= 4) { + offsets = []; + for (let j = 0; j < size; ++j) { + offsets.push(u8array[i] | (u8array[i + 1] << 8) | (u8array[i + 2] << 16) | + (u8array[i + 3] << 24)); + i += 4; } - const posBefore = parserState.pos; - getFilteredNextElem(query, parserState, elems, endChar !== ""); - if (endChar !== "" && parserState.pos >= parserState.length) { - throw ["Unclosed ", extra]; + } + for (let j = 0; j < size; ++j) { + if (offsets && offsets[j] !== i) { + console.log(this.containers); + throw new Error(`corrupt bitmap ${j}: ${i} / ${offsets[j]}`); } - // This case can be encountered if `getNextElem` encountered a "stop character" right - // from the start. For example if you have `,,` or `<>`. In this case, we simply move up - // the current position to continue the parsing. - if (posBefore === parserState.pos) { - parserState.pos += 1; + if (is_run[j >> 3] & (1 << (j & 0x7))) { + const runcount = (u8array[i] | (u8array[i + 1] << 8)); + i += 2; + this.containers.push(new RoaringBitmapRun( + runcount, + u8array.slice(i, i + (runcount * 4)), + )); + i += runcount * 4; + } else if (this.cardinalities[j] >= 4096) { + this.containers.push(new RoaringBitmapBits(u8array.slice(i, i + 8192))); + i += 8192; + } else { + const end = this.cardinalities[j] * 2; + this.containers.push(new RoaringBitmapArray( + this.cardinalities[j], + u8array.slice(i, i + end), + )); + i += end; } - foundStopChar = false; } - if (parserState.pos >= parserState.length && endChar !== "") { - throw ["Unclosed ", extra]; + } + contains(keyvalue) { + const key = keyvalue >> 16; + const value = keyvalue & 0xFFFF; + for (let i = 0; i < this.keys.length; ++i) { + if (this.keys[i] === key) { + return this.containers[i].contains(value); + } } - // We are either at the end of the string or on the `endChar` character, let's move forward - // in any case. - parserState.pos += 1; + return false; + } +} - if (hofParameters) { - // Commas in a HOF don't cause wrapping parens to become a tuple. - // If you want a one-tuple with a HOF in it, write `((a -> b),)`. - foundSeparator = false; - // HOFs can't have directly nested bindings. - if ([...elems, ...hofParameters].some(x => x.bindingName) || parserState.isInBinding) { - throw ["Unexpected ", "=", " within ", "->"]; - } - // HOFs are represented the same way closures are. - // The arguments are wrapped in a tuple, and the output - // is a binding, even though the compiler doesn't technically - // represent fn pointers that way. - const hofElem = makePrimitiveElement("->", { - generics: hofParameters, - bindings: new Map([["output", [...elems]]]), - typeFilter: null, - }); - elems.length = 0; - elems[0] = hofElem; +class RoaringBitmapRun { + constructor(runcount, array) { + this.runcount = runcount; + this.array = array; + } + contains(value) { + const l = this.runcount * 4; + for (let i = 0; i < l; i += 4) { + const start = this.array[i] | (this.array[i + 1] << 8); + const lenm1 = this.array[i + 2] | (this.array[i + 3] << 8); + if (value >= start && value <= (start + lenm1)) { + return true; + } } + return false; + } +} +class RoaringBitmapArray { + constructor(cardinality, array) { + this.cardinality = cardinality; + this.array = array; + } + contains(value) { + const l = this.cardinality * 2; + for (let i = 0; i < l; i += 2) { + const start = this.array[i] | (this.array[i + 1] << 8); + if (value === start) { + return true; + } + } + return false; + } +} +class RoaringBitmapBits { + constructor(array) { + this.array = array; + } + contains(value) { + return !!(this.array[value >> 3] & (1 << (value & 7))); + } +} + + +class DocSearch { + constructor(rawSearchIndex, rootPath, searchState) { + /** + * @type {Map<String, RoaringBitmap>} + */ + this.searchIndexDeprecated = new Map(); + /** + * @type {Map<String, RoaringBitmap>} + */ + this.searchIndexEmptyDesc = new Map(); + /** + * @type {Uint32Array} + */ + this.functionTypeFingerprint = null; + /** + * Map from normalized type names to integers. Used to make type search + * more efficient. + * + * @type {Map<string, {id: integer, assocOnly: boolean}>} + */ + this.typeNameIdMap = new Map(); + this.ALIASES = new Map(); + this.rootPath = rootPath; + this.searchState = searchState; + + /** + * Special type name IDs for searching by array. + */ + this.typeNameIdOfArray = this.buildTypeMapIndex("array"); + /** + * Special type name IDs for searching by slice. + */ + this.typeNameIdOfSlice = this.buildTypeMapIndex("slice"); + /** + * Special type name IDs for searching by both array and slice (`[]` syntax). + */ + this.typeNameIdOfArrayOrSlice = this.buildTypeMapIndex("[]"); + /** + * Special type name IDs for searching by tuple. + */ + this.typeNameIdOfTuple = this.buildTypeMapIndex("tuple"); + /** + * Special type name IDs for searching by unit. + */ + this.typeNameIdOfUnit = this.buildTypeMapIndex("unit"); + /** + * Special type name IDs for searching by both tuple and unit (`()` syntax). + */ + this.typeNameIdOfTupleOrUnit = this.buildTypeMapIndex("()"); + /** + * Special type name IDs for searching `fn`. + */ + this.typeNameIdOfFn = this.buildTypeMapIndex("fn"); + /** + * Special type name IDs for searching `fnmut`. + */ + this.typeNameIdOfFnMut = this.buildTypeMapIndex("fnmut"); + /** + * Special type name IDs for searching `fnonce`. + */ + this.typeNameIdOfFnOnce = this.buildTypeMapIndex("fnonce"); + /** + * Special type name IDs for searching higher order functions (`->` syntax). + */ + this.typeNameIdOfHof = this.buildTypeMapIndex("->"); + + /** + * Empty, immutable map used in item search types with no bindings. + * + * @type {Map<number, Array<FunctionType>>} + */ + this.EMPTY_BINDINGS_MAP = new Map(); - parserState.typeFilter = oldTypeFilter; - parserState.isInBinding = oldIsInBinding; + /** + * Empty, immutable map used in item search types with no bindings. + * + * @type {Array<FunctionType>} + */ + this.EMPTY_GENERICS_ARRAY = []; + + /** + * Object pool for function types with no bindings or generics. + * This is reset after loading the index. + * + * @type {Map<number|null, FunctionType>} + */ + this.TYPES_POOL = new Map(); - return { foundSeparator }; + /** + * @type {Array<Row>} + */ + this.searchIndex = this.buildIndex(rawSearchIndex); } /** - * Checks that the type filter doesn't have unwanted characters like `<>` (which are ignored - * if empty). + * Add an item to the type Name->ID map, or, if one already exists, use it. + * Returns the number. If name is "" or null, return null (pure generic). + * + * This is effectively string interning, so that function matching can be + * done more quickly. Two types with the same name but different item kinds + * get the same ID. * - * @param {ParserState} parserState + * @param {string} name + * @param {boolean} isAssocType - True if this is an assoc type + * + * @returns {integer} */ - function checkExtraTypeFilterCharacters(start, parserState) { - const query = parserState.userQuery.slice(start, parserState.pos).trim(); + buildTypeMapIndex(name, isAssocType) { + if (name === "" || name === null) { + return null; + } - const match = query.match(REGEX_INVALID_TYPE_FILTER); - if (match) { - throw [ - "Unexpected ", - match[0], - " in type filter (before ", - ":", - ")", - ]; + if (this.typeNameIdMap.has(name)) { + const obj = this.typeNameIdMap.get(name); + obj.assocOnly = isAssocType && obj.assocOnly; + return obj.id; + } else { + const id = this.typeNameIdMap.size; + this.typeNameIdMap.set(name, { id, assocOnly: isAssocType }); + return id; } } /** - * Parses the provided `query` input to fill `parserState`. If it encounters an error while - * parsing `query`, it'll throw an error. + * Convert a list of RawFunctionType / ID to object-based FunctionType. + * + * Crates often have lots of functions in them, and it's common to have a large number of + * functions that operate on a small set of data types, so the search index compresses them + * by encoding function parameter and return types as indexes into an array of names. * - * @param {ParsedQuery} query - * @param {ParserState} parserState + * Even when a general-purpose compression algorithm is used, this is still a win. + * I checked. https://github.com/rust-lang/rust/pull/98475#issue-1284395985 + * + * The format for individual function types is encoded in + * librustdoc/html/render/mod.rs: impl Serialize for RenderType + * + * @param {null|Array<RawFunctionType>} types + * @param {Array<{name: string, ty: number}>} lowercasePaths + * + * @return {Array<FunctionSearchType>} */ - function parseInput(query, parserState) { - let foundStopChar = true; - - while (parserState.pos < parserState.length) { - const c = parserState.userQuery[parserState.pos]; - if (isEndCharacter(c)) { - foundStopChar = true; - if (isSeparatorCharacter(c)) { - parserState.pos += 1; - continue; - } else if (c === "-" || c === ">") { - if (isReturnArrow(parserState)) { - break; - } - throw ["Unexpected ", c, " (did you mean ", "->", "?)"]; - } else if (parserState.pos > 0) { - throw ["Unexpected ", c, " after ", parserState.userQuery[parserState.pos - 1]]; - } - throw ["Unexpected ", c]; - } else if (c === " ") { - skipWhitespace(parserState); - continue; - } - if (!foundStopChar) { - let extra = ""; - if (isLastElemGeneric(query.elems, parserState)) { - extra = [" after ", ">"]; - } else if (prevIs(parserState, "\"")) { - throw ["Cannot have more than one element if you use quotes"]; - } - if (parserState.typeFilter !== null) { - throw [ - "Expected ", - ",", - " or ", - "->", - ...extra, - ", found ", - c, + buildItemSearchTypeAll(types, lowercasePaths) { + return types.length > 0 ? + types.map(type => this.buildItemSearchType(type, lowercasePaths)) : + this.EMPTY_GENERICS_ARRAY; + } + + /** + * Converts a single type. + * + * @param {RawFunctionType} type + */ + buildItemSearchType(type, lowercasePaths, isAssocType) { + const PATH_INDEX_DATA = 0; + const GENERICS_DATA = 1; + const BINDINGS_DATA = 2; + let pathIndex, generics, bindings; + if (typeof type === "number") { + pathIndex = type; + generics = this.EMPTY_GENERICS_ARRAY; + bindings = this.EMPTY_BINDINGS_MAP; + } else { + pathIndex = type[PATH_INDEX_DATA]; + generics = this.buildItemSearchTypeAll( + type[GENERICS_DATA], + lowercasePaths, + ); + if (type.length > BINDINGS_DATA && type[BINDINGS_DATA].length > 0) { + bindings = new Map(type[BINDINGS_DATA].map(binding => { + const [assocType, constraints] = binding; + // Associated type constructors are represented sloppily in rustdoc's + // type search, to make the engine simpler. + // + // MyType<Output<T>=Result<T>> is equivalent to MyType<Output<Result<T>>=T> + // and both are, essentially + // MyType<Output=(T, Result<T>)>, except the tuple isn't actually there. + // It's more like the value of a type binding is naturally an array, + // which rustdoc calls "constraints". + // + // As a result, the key should never have generics on it. + return [ + this.buildItemSearchType(assocType, lowercasePaths, true).id, + this.buildItemSearchTypeAll(constraints, lowercasePaths), ]; - } - throw [ - "Expected ", - ",", - ", ", - ":", - " or ", - "->", - ...extra, - ", found ", - c, - ]; - } - const before = query.elems.length; - getFilteredNextElem(query, parserState, query.elems, false); - if (query.elems.length === before) { - // Nothing was added, weird... Let's increase the position to not remain stuck. - parserState.pos += 1; + })); + } else { + bindings = this.EMPTY_BINDINGS_MAP; } - foundStopChar = false; } - if (parserState.typeFilter !== null) { - throw [ - "Unexpected ", - ":", - " (expected path after type filter ", - parserState.typeFilter + ":", - ")", - ]; + /** + * @type {FunctionType} + */ + let result; + if (pathIndex < 0) { + // types less than 0 are generic parameters + // the actual names of generic parameters aren't stored, since they aren't API + result = { + id: pathIndex, + ty: TY_GENERIC, + path: null, + exactPath: null, + generics, + bindings, + }; + } else if (pathIndex === 0) { + // `0` is used as a sentinel because it's fewer bytes than `null` + result = { + id: null, + ty: null, + path: null, + exactPath: null, + generics, + bindings, + }; + } else { + const item = lowercasePaths[pathIndex - 1]; + result = { + id: this.buildTypeMapIndex(item.name, isAssocType), + ty: item.ty, + path: item.path, + exactPath: item.exactPath, + generics, + bindings, + }; } - while (parserState.pos < parserState.length) { - if (isReturnArrow(parserState)) { - parserState.pos += 2; - skipWhitespace(parserState); - // Get returned elements. - getItemsBefore(query, parserState, query.returned, ""); - // Nothing can come afterward! - if (query.returned.length === 0) { - throw ["Expected at least one item after ", "->"]; + const cr = this.TYPES_POOL.get(result.id); + if (cr) { + // Shallow equality check. Since this function is used + // to construct every type object, this should be mostly + // equivalent to a deep equality check, except if there's + // a conflict, we don't keep the old one around, so it's + // not a fully precise implementation of hashcons. + if (cr.generics.length === result.generics.length && + cr.generics !== result.generics && + cr.generics.every((x, i) => result.generics[i] === x) + ) { + result.generics = cr.generics; + } + if (cr.bindings.size === result.bindings.size && cr.bindings !== result.bindings) { + let ok = true; + for (const [k, v] of cr.bindings.entries()) { + const v2 = result.bindings.get(v); + if (!v2) { + ok = false; + break; + } + if (v !== v2 && v.length === v2.length && v.every((x, i) => v2[i] === x)) { + result.bindings.set(k, v); + } else if (v !== v2) { + ok = false; + break; + } + } + if (ok) { + result.bindings = cr.bindings; } - break; - } else { - parserState.pos += 1; + } + if (cr.ty === result.ty && cr.path === result.path + && cr.bindings === result.bindings && cr.generics === result.generics + && cr.ty === result.ty + ) { + return cr; } } + this.TYPES_POOL.set(result.id, result); + return result; } /** - * Takes the user search input and returns an empty `ParsedQuery`. + * Type fingerprints allow fast, approximate matching of types. * - * @param {string} userQuery + * This algo creates a compact representation of the type set using a Bloom filter. + * This fingerprint is used three ways: + * + * - It accelerates the matching algorithm by checking the function fingerprint against the + * query fingerprint. If any bits are set in the query but not in the function, it can't + * match. + * + * - The fourth section has the number of distinct items in the set. + * This is the distance function, used for filtering and for sorting. * - * @return {ParsedQuery} + * [^1]: Distance is the relatively naive metric of counting the number of distinct items in + * the function that are not present in the query. + * + * @param {FunctionType|QueryElement} type - a single type + * @param {Uint32Array} output - write the fingerprint to this data structure: uses 128 bits + * @param {Set<number>} fps - Set of distinct items */ - function newParsedQuery(userQuery) { - return { - original: userQuery, - userQuery: userQuery.toLowerCase(), - elems: [], - returned: [], - // Total number of "top" elements (does not include generics). - foundElems: 0, - // Total number of elements (includes generics). - totalElems: 0, - literalSearch: false, - error: null, - correction: null, - proposeCorrectionFrom: null, - proposeCorrectionTo: null, - // bloom filter build from type ids - typeFingerprint: new Uint32Array(4), + buildFunctionTypeFingerprint(type, output, fps) { + let input = type.id; + // All forms of `[]`/`()`/`->` get collapsed down to one thing in the bloom filter. + // Differentiating between arrays and slices, if the user asks for it, is + // still done in the matching algorithm. + if (input === this.typeNameIdOfArray || input === this.typeNameIdOfSlice) { + input = this.typeNameIdOfArrayOrSlice; + } + if (input === this.typeNameIdOfTuple || input === this.typeNameIdOfUnit) { + input = this.typeNameIdOfTupleOrUnit; + } + if (input === this.typeNameIdOfFn || input === this.typeNameIdOfFnMut || + input === this.typeNameIdOfFnOnce) { + input = this.typeNameIdOfHof; + } + // http://burtleburtle.net/bob/hash/integer.html + // ~~ is toInt32. It's used before adding, so + // the number stays in safe integer range. + const hashint1 = k => { + k = (~~k + 0x7ed55d16) + (k << 12); + k = (k ^ 0xc761c23c) ^ (k >>> 19); + k = (~~k + 0x165667b1) + (k << 5); + k = (~~k + 0xd3a2646c) ^ (k << 9); + k = (~~k + 0xfd7046c5) + (k << 3); + return (k ^ 0xb55a4f09) ^ (k >>> 16); + }; + const hashint2 = k => { + k = ~k + (k << 15); + k ^= k >>> 12; + k += k << 2; + k ^= k >>> 4; + k = Math.imul(k, 2057); + return k ^ (k >> 16); }; + if (input !== null) { + const h0a = hashint1(input); + const h0b = hashint2(input); + // Less Hashing, Same Performance: Building a Better Bloom Filter + // doi=10.1.1.72.2442 + const h1a = ~~(h0a + Math.imul(h0b, 2)); + const h1b = ~~(h0a + Math.imul(h0b, 3)); + const h2a = ~~(h0a + Math.imul(h0b, 4)); + const h2b = ~~(h0a + Math.imul(h0b, 5)); + output[0] |= (1 << (h0a % 32)) | (1 << (h1b % 32)); + output[1] |= (1 << (h1a % 32)) | (1 << (h2b % 32)); + output[2] |= (1 << (h2a % 32)) | (1 << (h0b % 32)); + fps.add(input); + } + for (const g of type.generics) { + this.buildFunctionTypeFingerprint(g, output, fps); + } + const fb = { + id: null, + ty: 0, + generics: this.EMPTY_GENERICS_ARRAY, + bindings: this.EMPTY_BINDINGS_MAP, + }; + for (const [k, v] of type.bindings.entries()) { + fb.id = k; + fb.generics = v; + this.buildFunctionTypeFingerprint(fb, output, fps); + } + output[3] = fps.size; } /** - * Build an URL with search parameters. - * - * @param {string} search - The current search being performed. - * @param {string|null} filterCrates - The current filtering crate (if any). + * Convert raw search index into in-memory search index. * - * @return {string} + * @param {[string, RawSearchIndexCrate][]} rawSearchIndex */ - function buildUrl(search, filterCrates) { - let extra = "?search=" + encodeURIComponent(search); + buildIndex(rawSearchIndex) { + /** + * Convert from RawFunctionSearchType to FunctionSearchType. + * + * Crates often have lots of functions in them, and function signatures are sometimes + * complex, so rustdoc uses a pretty tight encoding for them. This function converts it + * to a simpler, object-based encoding so that the actual search code is more readable + * and easier to debug. + * + * The raw function search type format is generated using serde in + * librustdoc/html/render/mod.rs: IndexItemFunctionType::write_to_string + * + * @param {Array<{name: string, ty: number}>} lowercasePaths + * + * @return {null|FunctionSearchType} + */ + const buildFunctionSearchTypeCallback = lowercasePaths => { + return functionSearchType => { + if (functionSearchType === 0) { + return null; + } + const INPUTS_DATA = 0; + const OUTPUT_DATA = 1; + let inputs, output; + if (typeof functionSearchType[INPUTS_DATA] === "number") { + inputs = [ + this.buildItemSearchType(functionSearchType[INPUTS_DATA], lowercasePaths), + ]; + } else { + inputs = this.buildItemSearchTypeAll( + functionSearchType[INPUTS_DATA], + lowercasePaths, + ); + } + if (functionSearchType.length > 1) { + if (typeof functionSearchType[OUTPUT_DATA] === "number") { + output = [ + this.buildItemSearchType( + functionSearchType[OUTPUT_DATA], + lowercasePaths, + ), + ]; + } else { + output = this.buildItemSearchTypeAll( + functionSearchType[OUTPUT_DATA], + lowercasePaths, + ); + } + } else { + output = []; + } + const where_clause = []; + const l = functionSearchType.length; + for (let i = 2; i < l; ++i) { + where_clause.push(typeof functionSearchType[i] === "number" + ? [this.buildItemSearchType(functionSearchType[i], lowercasePaths)] + : this.buildItemSearchTypeAll(functionSearchType[i], lowercasePaths)); + } + return { + inputs, output, where_clause, + }; + }; + }; + + const searchIndex = []; + let currentIndex = 0; + let id = 0; - if (filterCrates !== null) { - extra += "&filter-crate=" + encodeURIComponent(filterCrates); + // Function type fingerprints are 128-bit bloom filters that are used to + // estimate the distance between function and query. + // This loop counts the number of items to allocate a fingerprint for. + for (const crate of rawSearchIndex.values()) { + // Each item gets an entry in the fingerprint array, and the crate + // does, too + id += crate.t.length + 1; } - return getNakedUrl() + extra + window.location.hash; - } + this.functionTypeFingerprint = new Uint32Array((id + 1) * 4); + // This loop actually generates the search item indexes, including + // normalized names, type signature objects and fingerprints, and aliases. + id = 0; - /** - * Return the filtering crate or `null` if there is none. - * - * @return {string|null} - */ - function getFilterCrates() { - const elem = document.getElementById("crate-search"); + for (const [crate, crateCorpus] of rawSearchIndex) { + // a string representing the lengths of each description shard + // a string representing the list of function types + const itemDescShardDecoder = new VlqHexDecoder(crateCorpus.D, noop => noop); + let descShard = { + crate, + shard: 0, + start: 0, + len: itemDescShardDecoder.next(), + promise: null, + resolve: null, + }; + const descShardList = [descShard]; - if (elem && - elem.value !== "all crates" && - rawSearchIndex.has(elem.value) - ) { - return elem.value; + // Deprecated items and items with no description + this.searchIndexDeprecated.set(crate, new RoaringBitmap(crateCorpus.c)); + this.searchIndexEmptyDesc.set(crate, new RoaringBitmap(crateCorpus.e)); + let descIndex = 0; + + // This object should have exactly the same set of fields as the "row" + // object defined below. Your JavaScript runtime will thank you. + // https://mathiasbynens.be/notes/shapes-ics + const crateRow = { + crate, + ty: 3, // == ExternCrate + name: crate, + path: "", + descShard, + descIndex, + exactPath: "", + desc: crateCorpus.doc, + parent: undefined, + type: null, + id, + word: crate, + normalizedName: crate.indexOf("_") === -1 ? crate : crate.replace(/_/g, ""), + bitIndex: 0, + implDisambiguator: null, + }; + id += 1; + searchIndex.push(crateRow); + currentIndex += 1; + if (!this.searchIndexEmptyDesc.get(crate).contains(0)) { + descIndex += 1; + } + + // a String of one character item type codes + const itemTypes = crateCorpus.t; + // an array of (String) item names + const itemNames = crateCorpus.n; + // an array of [(Number) item index, + // (String) full path] + // an item whose index is not present will fall back to the previous present path + // i.e. if indices 4 and 11 are present, but 5-10 and 12-13 are not present, + // 5-10 will fall back to the path for 4 and 12-13 will fall back to the path for 11 + const itemPaths = new Map(crateCorpus.q); + // An array of [(Number) item index, (Number) path index] + // Used to de-duplicate inlined and re-exported stuff + const itemReexports = new Map(crateCorpus.r); + // an array of (Number) the parent path index + 1 to `paths`, or 0 if none + const itemParentIdxDecoder = new VlqHexDecoder(crateCorpus.i, noop => noop); + // a map Number, string for impl disambiguators + const implDisambiguator = new Map(crateCorpus.b); + // an array of [(Number) item type, + // (String) name] + const paths = crateCorpus.p; + // an array of [(String) alias name + // [Number] index to items] + const aliases = crateCorpus.a; + + // an array of [{name: String, ty: Number}] + const lowercasePaths = []; + + // a string representing the list of function types + const itemFunctionDecoder = new VlqHexDecoder( + crateCorpus.f, + buildFunctionSearchTypeCallback(lowercasePaths), + ); + + // convert `rawPaths` entries into object form + // generate normalizedPaths for function search mode + let len = paths.length; + let lastPath = itemPaths.get(0); + for (let i = 0; i < len; ++i) { + const elem = paths[i]; + const ty = elem[0]; + const name = elem[1]; + let path = null; + if (elem.length > 2) { + path = itemPaths.has(elem[2]) ? itemPaths.get(elem[2]) : lastPath; + lastPath = path; + } + const exactPath = elem.length > 3 ? itemPaths.get(elem[3]) : path; + + lowercasePaths.push({ ty, name: name.toLowerCase(), path, exactPath }); + paths[i] = { ty, name, path, exactPath }; + } + + // convert `item*` into an object form, and construct word indices. + // + // before any analysis is performed lets gather the search terms to + // search against apart from the rest of the data. This is a quick + // operation that is cached for the life of the page state so that + // all other search operations have access to this cached data for + // faster analysis operations + lastPath = ""; + len = itemTypes.length; + let lastName = ""; + let lastWord = ""; + for (let i = 0; i < len; ++i) { + const bitIndex = i + 1; + if (descIndex >= descShard.len && + !this.searchIndexEmptyDesc.get(crate).contains(bitIndex)) { + descShard = { + crate, + shard: descShard.shard + 1, + start: descShard.start + descShard.len, + len: itemDescShardDecoder.next(), + promise: null, + resolve: null, + }; + descIndex = 0; + descShardList.push(descShard); + } + const name = itemNames[i] === "" ? lastName : itemNames[i]; + const word = itemNames[i] === "" ? lastWord : itemNames[i].toLowerCase(); + const path = itemPaths.has(i) ? itemPaths.get(i) : lastPath; + const type = itemFunctionDecoder.next(); + if (type !== null) { + if (type) { + const fp = this.functionTypeFingerprint.subarray(id * 4, (id + 1) * 4); + const fps = new Set(); + for (const t of type.inputs) { + this.buildFunctionTypeFingerprint(t, fp, fps); + } + for (const t of type.output) { + this.buildFunctionTypeFingerprint(t, fp, fps); + } + for (const w of type.where_clause) { + for (const t of w) { + this.buildFunctionTypeFingerprint(t, fp, fps); + } + } + } + } + // This object should have exactly the same set of fields as the "crateRow" + // object defined above. + const itemParentIdx = itemParentIdxDecoder.next(); + const row = { + crate, + ty: itemTypes.charCodeAt(i) - 65, // 65 = "A" + name, + path, + descShard, + descIndex, + exactPath: itemReexports.has(i) ? + itemPaths.get(itemReexports.get(i)) : path, + parent: itemParentIdx > 0 ? paths[itemParentIdx - 1] : undefined, + type, + id, + word, + normalizedName: word.indexOf("_") === -1 ? word : word.replace(/_/g, ""), + bitIndex, + implDisambiguator: implDisambiguator.has(i) ? + implDisambiguator.get(i) : null, + }; + id += 1; + searchIndex.push(row); + lastPath = row.path; + if (!this.searchIndexEmptyDesc.get(crate).contains(bitIndex)) { + descIndex += 1; + } + lastName = name; + lastWord = word; + } + + if (aliases) { + const currentCrateAliases = new Map(); + this.ALIASES.set(crate, currentCrateAliases); + for (const alias_name in aliases) { + if (!Object.prototype.hasOwnProperty.call(aliases, alias_name)) { + continue; + } + + let currentNameAliases; + if (currentCrateAliases.has(alias_name)) { + currentNameAliases = currentCrateAliases.get(alias_name); + } else { + currentNameAliases = []; + currentCrateAliases.set(alias_name, currentNameAliases); + } + for (const local_alias of aliases[alias_name]) { + currentNameAliases.push(local_alias + currentIndex); + } + } + } + currentIndex += itemTypes.length; + this.searchState.descShards.set(crate, descShardList); } - return null; + // Drop the (rather large) hash table used for reusing function items + this.TYPES_POOL = new Map(); + return searchIndex; } /** @@ -1249,7 +1748,15 @@ function initSearch(rawSearchIndex) { * * @return {ParsedQuery} - The parsed query */ - function parseQuery(userQuery) { + static parseQuery(userQuery) { + function itemTypeFromName(typename) { + const index = itemTypes.findIndex(i => i === typename); + if (index < 0) { + throw ["Unknown type filter ", typename]; + } + return index; + } + function convertTypeFilterOnElem(elem) { if (elem.typeFilter !== null) { let typeFilter = elem.typeFilter; @@ -1269,6 +1776,130 @@ function initSearch(rawSearchIndex) { } } } + + /** + * Takes the user search input and returns an empty `ParsedQuery`. + * + * @param {string} userQuery + * + * @return {ParsedQuery} + */ + function newParsedQuery(userQuery) { + return { + original: userQuery, + userQuery: userQuery.toLowerCase(), + elems: [], + returned: [], + // Total number of "top" elements (does not include generics). + foundElems: 0, + // Total number of elements (includes generics). + totalElems: 0, + literalSearch: false, + error: null, + correction: null, + proposeCorrectionFrom: null, + proposeCorrectionTo: null, + // bloom filter build from type ids + typeFingerprint: new Uint32Array(4), + }; + } + + /** + * Parses the provided `query` input to fill `parserState`. If it encounters an error while + * parsing `query`, it'll throw an error. + * + * @param {ParsedQuery} query + * @param {ParserState} parserState + */ + function parseInput(query, parserState) { + let foundStopChar = true; + + while (parserState.pos < parserState.length) { + const c = parserState.userQuery[parserState.pos]; + if (isEndCharacter(c)) { + foundStopChar = true; + if (isSeparatorCharacter(c)) { + parserState.pos += 1; + continue; + } else if (c === "-" || c === ">") { + if (isReturnArrow(parserState)) { + break; + } + throw ["Unexpected ", c, " (did you mean ", "->", "?)"]; + } else if (parserState.pos > 0) { + throw ["Unexpected ", c, " after ", + parserState.userQuery[parserState.pos - 1]]; + } + throw ["Unexpected ", c]; + } else if (c === " ") { + skipWhitespace(parserState); + continue; + } + if (!foundStopChar) { + let extra = ""; + if (isLastElemGeneric(query.elems, parserState)) { + extra = [" after ", ">"]; + } else if (prevIs(parserState, "\"")) { + throw ["Cannot have more than one element if you use quotes"]; + } + if (parserState.typeFilter !== null) { + throw [ + "Expected ", + ",", + " or ", + "->", + ...extra, + ", found ", + c, + ]; + } + throw [ + "Expected ", + ",", + ", ", + ":", + " or ", + "->", + ...extra, + ", found ", + c, + ]; + } + const before = query.elems.length; + getFilteredNextElem(query, parserState, query.elems, false); + if (query.elems.length === before) { + // Nothing was added, weird... Let's increase the position to not remain stuck. + parserState.pos += 1; + } + foundStopChar = false; + } + if (parserState.typeFilter !== null) { + throw [ + "Unexpected ", + ":", + " (expected path after type filter ", + parserState.typeFilter + ":", + ")", + ]; + } + while (parserState.pos < parserState.length) { + if (isReturnArrow(parserState)) { + parserState.pos += 2; + skipWhitespace(parserState); + // Get returned elements. + getItemsBefore(query, parserState, query.returned, ""); + // Nothing can come afterward! + if (query.returned.length === 0) { + throw ["Expected at least one item after ", "->"]; + } + break; + } else { + parserState.pos += 1; + } + } + } + + userQuery = userQuery.trim().replace(/\r|\n|\t/g, " "); const parserState = { length: userQuery.length, @@ -1306,25 +1937,6 @@ function initSearch(rawSearchIndex) { } /** - * Creates the query results. - * - * @param {Array<Result>} results_in_args - * @param {Array<Result>} results_returned - * @param {Array<Result>} results_others - * @param {ParsedQuery} parsedQuery - * - * @return {ResultsTable} - */ - function createQueryResults(results_in_args, results_returned, results_others, parsedQuery) { - return { - "in_args": results_in_args, - "returned": results_returned, - "others": results_others, - "query": parsedQuery, - }; - } - - /** * Executes the parsed query and builds a {ResultsTable}. * * @param {ParsedQuery} parsedQuery - The parsed user query @@ -1333,24 +1945,116 @@ function initSearch(rawSearchIndex) { * * @return {ResultsTable} */ - async function execQuery(parsedQuery, filterCrates, currentCrate) { + async execQuery(parsedQuery, filterCrates, currentCrate) { const results_others = new Map(), results_in_args = new Map(), results_returned = new Map(); /** + * Creates the query results. + * + * @param {Array<Result>} results_in_args + * @param {Array<Result>} results_returned + * @param {Array<Result>} results_others + * @param {ParsedQuery} parsedQuery + * + * @return {ResultsTable} + */ + function createQueryResults( + results_in_args, + results_returned, + results_others, + parsedQuery) { + return { + "in_args": results_in_args, + "returned": results_returned, + "others": results_others, + "query": parsedQuery, + }; + } + + const buildHrefAndPath = item => { + let displayPath; + let href; + const type = itemTypes[item.ty]; + const name = item.name; + let path = item.path; + let exactPath = item.exactPath; + + if (type === "mod") { + displayPath = path + "::"; + href = this.rootPath + path.replace(/::/g, "/") + "/" + + name + "/index.html"; + } else if (type === "import") { + displayPath = item.path + "::"; + href = this.rootPath + item.path.replace(/::/g, "/") + + "/index.html#reexport." + name; + } else if (type === "primitive" || type === "keyword") { + displayPath = ""; + href = this.rootPath + path.replace(/::/g, "/") + + "/" + type + "." + name + ".html"; + } else if (type === "externcrate") { + displayPath = ""; + href = this.rootPath + name + "/index.html"; + } else if (item.parent !== undefined) { + const myparent = item.parent; + let anchor = type + "." + name; + const parentType = itemTypes[myparent.ty]; + let pageType = parentType; + let pageName = myparent.name; + exactPath = `${myparent.exactPath}::${myparent.name}`; + + if (parentType === "primitive") { + displayPath = myparent.name + "::"; + } else if (type === "structfield" && parentType === "variant") { + // Structfields belonging to variants are special: the + // final path element is the enum name. + const enumNameIdx = item.path.lastIndexOf("::"); + const enumName = item.path.substr(enumNameIdx + 2); + path = item.path.substr(0, enumNameIdx); + displayPath = path + "::" + enumName + "::" + myparent.name + "::"; + anchor = "variant." + myparent.name + ".field." + name; + pageType = "enum"; + pageName = enumName; + } else { + displayPath = path + "::" + myparent.name + "::"; + } + if (item.implDisambiguator !== null) { + anchor = item.implDisambiguator + "/" + anchor; + } + href = this.rootPath + path.replace(/::/g, "/") + + "/" + pageType + + "." + pageName + + ".html#" + anchor; + } else { + displayPath = item.path + "::"; + href = this.rootPath + item.path.replace(/::/g, "/") + + "/" + type + "." + name + ".html"; + } + return [displayPath, href, `${exactPath}::${name}`]; + }; + + function pathSplitter(path) { + const tmp = "<span>" + path.replace(/::/g, "::</span><span>"); + if (tmp.endsWith("<span>")) { + return tmp.slice(0, tmp.length - 6); + } + return tmp; + } + + /** * Add extra data to result objects, and filter items that have been * marked for removal. * * @param {[ResultObject]} results * @returns {[ResultObject]} */ - function transformResults(results) { + const transformResults = results => { const duplicates = new Set(); const out = []; for (const result of results) { if (result.id !== -1) { - const obj = searchIndex[result.id]; + const obj = this.searchIndex[result.id]; obj.dist = result.dist; const res = buildHrefAndPath(obj); obj.displayPath = pathSplitter(res[0]); @@ -1380,7 +2084,7 @@ function initSearch(rawSearchIndex) { } } return out; - } + }; /** * This function takes a result map, and sorts it by various criteria, including edit @@ -1391,13 +2095,13 @@ function initSearch(rawSearchIndex) { * @param {string} preferredCrate * @returns {Promise<[ResultObject]>} */ - async function sortResults(results, isType, preferredCrate) { + const sortResults = async(results, isType, preferredCrate) => { const userQuery = parsedQuery.userQuery; const casedUserQuery = parsedQuery.original; const result_list = []; for (const result of results.values()) { - result.item = searchIndex[result.id]; - result.word = searchIndex[result.id].word; + result.item = this.searchIndex[result.id]; + result.word = this.searchIndex[result.id].word; result_list.push(result); } @@ -1449,8 +2153,8 @@ function initSearch(rawSearchIndex) { } // sort deprecated items later - a = searchIndexDeprecated.get(aaa.item.crate).contains(aaa.item.bitIndex); - b = searchIndexDeprecated.get(bbb.item.crate).contains(bbb.item.bitIndex); + a = this.searchIndexDeprecated.get(aaa.item.crate).contains(aaa.item.bitIndex); + b = this.searchIndexDeprecated.get(bbb.item.crate).contains(bbb.item.bitIndex); if (a !== b) { return a - b; } @@ -1477,8 +2181,8 @@ function initSearch(rawSearchIndex) { } // sort by description (no description goes later) - a = searchIndexEmptyDesc.get(aaa.item.crate).contains(aaa.item.bitIndex); - b = searchIndexEmptyDesc.get(bbb.item.crate).contains(bbb.item.bitIndex); + a = this.searchIndexEmptyDesc.get(aaa.item.crate).contains(aaa.item.bitIndex); + b = this.searchIndexEmptyDesc.get(bbb.item.crate).contains(bbb.item.bitIndex); if (a !== b) { return a - b; } @@ -1502,7 +2206,7 @@ function initSearch(rawSearchIndex) { }); return transformResults(result_list); - } + }; /** * This function checks if a list of search query `queryElems` can all be found in the @@ -1601,7 +2305,7 @@ function initSearch(rawSearchIndex) { return true; } } else if (unifyFunctionTypes( - [...fnType.generics, ...Array.from(fnType.bindings.values()).flat() ], + [...fnType.generics, ...Array.from(fnType.bindings.values()).flat()], queryElems, whereClause, mgens ? new Map(mgens) : null, @@ -1766,7 +2470,7 @@ function initSearch(rawSearchIndex) { * @param {Map<number,number>|null} mgensIn - Map functions generics to query generics. * @returns {boolean} */ - function unifyFunctionTypeIsMatchCandidate(fnType, queryElem, mgensIn) { + const unifyFunctionTypeIsMatchCandidate = (fnType, queryElem, mgensIn) => { // type filters look like `trait:Read` or `enum:Result` if (!typePassesFilter(queryElem.typeFilter, fnType.ty)) { return false; @@ -1792,19 +2496,19 @@ function initSearch(rawSearchIndex) { } return true; } else { - if (queryElem.id === typeNameIdOfArrayOrSlice && - (fnType.id === typeNameIdOfSlice || fnType.id === typeNameIdOfArray) + if (queryElem.id === this.typeNameIdOfArrayOrSlice && + (fnType.id === this.typeNameIdOfSlice || fnType.id === this.typeNameIdOfArray) ) { // [] matches primitive:array or primitive:slice // if it matches, then we're fine, and this is an appropriate match candidate - } else if (queryElem.id === typeNameIdOfTupleOrUnit && - (fnType.id === typeNameIdOfTuple || fnType.id === typeNameIdOfUnit) + } else if (queryElem.id === this.typeNameIdOfTupleOrUnit && + (fnType.id === this.typeNameIdOfTuple || fnType.id === this.typeNameIdOfUnit) ) { // () matches primitive:tuple or primitive:unit // if it matches, then we're fine, and this is an appropriate match candidate - } else if (queryElem.id === typeNameIdOfHof && - (fnType.id === typeNameIdOfFn || fnType.id === typeNameIdOfFnMut || - fnType.id === typeNameIdOfFnOnce) + } else if (queryElem.id === this.typeNameIdOfHof && + (fnType.id === this.typeNameIdOfFn || fnType.id === this.typeNameIdOfFnMut || + fnType.id === this.typeNameIdOfFnOnce) ) { // -> matches fn, fnonce, and fnmut // if it matches, then we're fine, and this is an appropriate match candidate @@ -1849,7 +2553,7 @@ function initSearch(rawSearchIndex) { } return true; } - } + }; /** * This function checks the associated type bindings. Any that aren't matched get converted * to generics, and this function returns an array of the function's generics with these @@ -1988,17 +2692,17 @@ function initSearch(rawSearchIndex) { } /** - * This function checks if the object (`row`) matches the given type (`elem`) and its - * generics (if any). - * - * @param {Array<FunctionType>} list - * @param {QueryElement} elem - The element from the parsed query. - * @param {[FunctionType]} whereClause - Trait bounds for generic items. - * @param {Map<number,number>|null} mgens - Map functions generics to query generics. - * @param {number} unboxingDepth - * - * @return {boolean} - Returns true if found, false otherwise. - */ + * This function checks if the object (`row`) matches the given type (`elem`) and its + * generics (if any). + * + * @param {Array<FunctionType>} list + * @param {QueryElement} elem - The element from the parsed query. + * @param {[FunctionType]} whereClause - Trait bounds for generic items. + * @param {Map<number,number>|null} mgens - Map functions generics to query generics. + * @param {number} unboxingDepth + * + * @return {boolean} - Returns true if found, false otherwise. + */ function checkIfInList(list, elem, whereClause, mgens, unboxingDepth) { for (const entry of list) { if (checkType(entry, elem, whereClause, mgens, unboxingDepth)) { @@ -2009,17 +2713,17 @@ function initSearch(rawSearchIndex) { } /** - * This function checks if the object (`row`) matches the given type (`elem`) and its - * generics (if any). - * - * @param {Row} row - * @param {QueryElement} elem - The element from the parsed query. - * @param {[FunctionType]} whereClause - Trait bounds for generic items. - * @param {Map<number,number>|null} mgens - Map functions generics to query generics. - * - * @return {boolean} - Returns true if the type matches, false otherwise. - */ - function checkType(row, elem, whereClause, mgens, unboxingDepth) { + * This function checks if the object (`row`) matches the given type (`elem`) and its + * generics (if any). + * + * @param {Row} row + * @param {QueryElement} elem - The element from the parsed query. + * @param {[FunctionType]} whereClause - Trait bounds for generic items. + * @param {Map<number,number>|null} mgens - Map functions generics to query generics. + * + * @return {boolean} - Returns true if the type matches, false otherwise. + */ + const checkType = (row, elem, whereClause, mgens, unboxingDepth) => { if (unboxingDepth >= UNBOXING_LIMIT) { return false; } @@ -2036,8 +2740,9 @@ function initSearch(rawSearchIndex) { if (row.id > 0 && elem.id > 0 && elem.pathWithoutLast.length === 0 && typePassesFilter(elem.typeFilter, row.ty) && elem.generics.length === 0 && // special case - elem.id !== typeNameIdOfArrayOrSlice && elem.id !== typeNameIdOfTupleOrUnit - && elem.id !== typeNameIdOfHof + elem.id !== this.typeNameIdOfArrayOrSlice + && elem.id !== this.typeNameIdOfTupleOrUnit + && elem.id !== this.typeNameIdOfHof ) { return row.id === elem.id || checkIfInList( row.generics, @@ -2049,7 +2754,7 @@ function initSearch(rawSearchIndex) { } } return unifyFunctionTypes([row], [elem], whereClause, mgens, null, unboxingDepth); - } + }; /** * Compute an "edit distance" that ignores missing path elements. @@ -2133,26 +2838,27 @@ function initSearch(rawSearchIndex) { }; } - async function handleAliases(ret, query, filterCrates, currentCrate) { + const handleAliases = async(ret, query, filterCrates, currentCrate) => { const lowerQuery = query.toLowerCase(); // We separate aliases and crate aliases because we want to have current crate // aliases to be before the others in the displayed results. const aliases = []; const crateAliases = []; if (filterCrates !== null) { - if (ALIASES.has(filterCrates) && ALIASES.get(filterCrates).has(lowerQuery)) { - const query_aliases = ALIASES.get(filterCrates).get(lowerQuery); + if (this.ALIASES.has(filterCrates) + && this.ALIASES.get(filterCrates).has(lowerQuery)) { + const query_aliases = this.ALIASES.get(filterCrates).get(lowerQuery); for (const alias of query_aliases) { - aliases.push(createAliasFromItem(searchIndex[alias])); + aliases.push(createAliasFromItem(this.searchIndex[alias])); } } } else { - for (const [crate, crateAliasesIndex] of ALIASES) { + for (const [crate, crateAliasesIndex] of this.ALIASES) { if (crateAliasesIndex.has(lowerQuery)) { const pushTo = crate === currentCrate ? crateAliases : aliases; const query_aliases = crateAliasesIndex.get(lowerQuery); for (const alias of query_aliases) { - pushTo.push(createAliasFromItem(searchIndex[alias])); + pushTo.push(createAliasFromItem(this.searchIndex[alias])); } } } @@ -2170,8 +2876,8 @@ function initSearch(rawSearchIndex) { aliases.sort(sortFunc); const fetchDesc = alias => { - return searchIndexEmptyDesc.get(alias.crate).contains(alias.bitIndex) ? - "" : searchState.loadDesc(alias); + return this.searchIndexEmptyDesc.get(alias.crate).contains(alias.bitIndex) ? + "" : this.searchState.loadDesc(alias); }; const [crateDescs, descs] = await Promise.all([ Promise.all(crateAliases.map(fetchDesc)), @@ -2199,7 +2905,7 @@ function initSearch(rawSearchIndex) { alias.desc = crateDescs[i]; }); crateAliases.forEach(pushFunc); - } + }; /** * This function adds the given result into the provided `results` map if it matches the @@ -2382,7 +3088,41 @@ function initSearch(rawSearchIndex) { addIntoResults(results, row.id, pos, 0, tfpDist, 0, Number.MAX_VALUE); } - function innerRunQuery() { + /** + * Compare the query fingerprint with the function fingerprint. + * + * @param {{number}} fullId - The function + * @param {{Uint32Array}} queryFingerprint - The query + * @returns {number|null} - Null if non-match, number if distance + * This function might return 0! + */ + const compareTypeFingerprints = (fullId, queryFingerprint) => { + const fh0 = this.functionTypeFingerprint[fullId * 4]; + const fh1 = this.functionTypeFingerprint[(fullId * 4) + 1]; + const fh2 = this.functionTypeFingerprint[(fullId * 4) + 2]; + const [qh0, qh1, qh2] = queryFingerprint; + // Approximate set intersection with bloom filters. + // This can be larger than reality, not smaller, because hashes have + // the property that if they've got the same value, they hash to the + // same thing. False positives exist, but not false negatives. + const [in0, in1, in2] = [fh0 & qh0, fh1 & qh1, fh2 & qh2]; + // Approximate the set of items in the query but not the function. + // This might be smaller than reality, but cannot be bigger. + // + // | in_ | qh_ | XOR | Meaning | + // | --- | --- | --- | ------------------------------------------------ | + // | 0 | 0 | 0 | Not present | + // | 1 | 0 | 1 | IMPOSSIBLE because `in_` is `fh_ & qh_` | + // | 1 | 1 | 0 | If one or both is false positive, false negative | + // | 0 | 1 | 1 | Since in_ has no false negatives, must be real | + if ((in0 ^ qh0) || (in1 ^ qh1) || (in2 ^ qh2)) { + return null; + } + return this.functionTypeFingerprint[(fullId * 4) + 3]; + }; + + + const innerRunQuery = () => { const queryLen = parsedQuery.elems.reduce((acc, next) => acc + next.pathLast.length, 0) + parsedQuery.returned.reduce((acc, next) => acc + next.pathLast.length, 0); @@ -2406,16 +3146,16 @@ function initSearch(rawSearchIndex) { * @param {QueryElement} elem * @param {boolean} isAssocType */ - function convertNameToId(elem, isAssocType) { + const convertNameToId = (elem, isAssocType) => { const loweredName = elem.pathLast.toLowerCase(); - if (typeNameIdMap.has(loweredName) && - (isAssocType || !typeNameIdMap.get(loweredName).assocOnly)) { - elem.id = typeNameIdMap.get(loweredName).id; + if (this.typeNameIdMap.has(loweredName) && + (isAssocType || !this.typeNameIdMap.get(loweredName).assocOnly)) { + elem.id = this.typeNameIdMap.get(loweredName).id; } else if (!parsedQuery.literalSearch) { let match = null; let matchDist = maxEditDistance + 1; let matchName = ""; - for (const [name, {id, assocOnly}] of typeNameIdMap) { + for (const [name, { id, assocOnly }] of this.typeNameIdMap) { const dist = Math.min( editDistance(name, loweredName, maxEditDistance), editDistance(name, elem.normalizedPathLast, maxEditDistance), @@ -2436,7 +3176,7 @@ function initSearch(rawSearchIndex) { elem.id = match; } if ((elem.id === null && parsedQuery.totalElems > 1 && elem.typeFilter === -1 - && elem.generics.length === 0 && elem.bindings.size === 0) + && elem.generics.length === 0 && elem.bindings.size === 0) || elem.typeFilter === TY_GENERIC) { if (genericSymbols.has(elem.name)) { elem.id = genericSymbols.get(elem.name); @@ -2451,7 +3191,7 @@ function initSearch(rawSearchIndex) { const maxPartDistance = Math.floor(elem.name.length / 3); let matchDist = maxPartDistance + 1; let matchName = ""; - for (const name of typeNameIdMap.keys()) { + for (const name of this.typeNameIdMap.keys()) { const dist = editDistance(name, elem.name, maxPartDistance); if (dist <= matchDist && dist <= maxPartDistance) { if (dist === matchDist && matchName > name) { @@ -2482,7 +3222,7 @@ function initSearch(rawSearchIndex) { elem.bindings = new Map(Array.from(elem.bindings.entries()) .map(entry => { const [name, constraints] = entry; - if (!typeNameIdMap.has(name)) { + if (!this.typeNameIdMap.has(name)) { parsedQuery.error = [ "Type parameter ", name, @@ -2494,29 +3234,30 @@ function initSearch(rawSearchIndex) { convertNameToId(elem2); } - return [typeNameIdMap.get(name).id, constraints]; + return [this.typeNameIdMap.get(name).id, constraints]; }), ); - } + }; const fps = new Set(); for (const elem of parsedQuery.elems) { convertNameToId(elem); - buildFunctionTypeFingerprint(elem, parsedQuery.typeFingerprint, fps); + this.buildFunctionTypeFingerprint(elem, parsedQuery.typeFingerprint, fps); } for (const elem of parsedQuery.returned) { convertNameToId(elem); - buildFunctionTypeFingerprint(elem, parsedQuery.typeFingerprint, fps); + this.buildFunctionTypeFingerprint(elem, parsedQuery.typeFingerprint, fps); } if (parsedQuery.foundElems === 1 && parsedQuery.returned.length === 0) { if (parsedQuery.elems.length === 1) { const elem = parsedQuery.elems[0]; - for (let i = 0, nSearchIndex = searchIndex.length; i < nSearchIndex; ++i) { + const length = this.searchIndex.length; + for (let i = 0, nSearchIndex = length; i < nSearchIndex; ++i) { // It means we want to check for this element everywhere (in names, args and // returned). handleSingleArg( - searchIndex[i], + this.searchIndex[i], i, elem, results_others, @@ -2543,11 +3284,11 @@ function initSearch(rawSearchIndex) { }; parsedQuery.elems.sort(sortQ); parsedQuery.returned.sort(sortQ); - for (let i = 0, nSearchIndex = searchIndex.length; i < nSearchIndex; ++i) { - handleArgs(searchIndex[i], i, results_others); + for (let i = 0, nSearchIndex = this.searchIndex.length; i < nSearchIndex; ++i) { + handleArgs(this.searchIndex[i], i, results_others); } } - } + }; if (parsedQuery.error === null) { innerRunQuery(); @@ -2567,9 +3308,9 @@ function initSearch(rawSearchIndex) { filterCrates, currentCrate); await Promise.all([ret.others, ret.returned, ret.in_args].map(async list => { const descs = await Promise.all(list.map(result => { - return searchIndexEmptyDesc.get(result.crate).contains(result.bitIndex) ? + return this.searchIndexEmptyDesc.get(result.crate).contains(result.bitIndex) ? "" : - searchState.loadDesc(result); + this.searchState.loadDesc(result); })); for (const [i, result] of list.entries()) { result.desc = descs[i]; @@ -2581,1310 +3322,610 @@ function initSearch(rawSearchIndex) { } return ret; } +} - function nextTab(direction) { - const next = (searchState.currentTab + direction + 3) % searchState.focusedByTab.length; - searchState.focusedByTab[searchState.currentTab] = document.activeElement; - printTab(next); - focusSearchResult(); - } - - // Focus the first search result on the active tab, or the result that - // was focused last time this tab was active. - function focusSearchResult() { - const target = searchState.focusedByTab[searchState.currentTab] || - document.querySelectorAll(".search-results.active a").item(0) || - document.querySelectorAll("#search-tabs button").item(searchState.currentTab); - searchState.focusedByTab[searchState.currentTab] = null; - if (target) { - target.focus(); - } - } - - function buildHrefAndPath(item) { - let displayPath; - let href; - const type = itemTypes[item.ty]; - const name = item.name; - let path = item.path; - let exactPath = item.exactPath; - - if (type === "mod") { - displayPath = path + "::"; - href = ROOT_PATH + path.replace(/::/g, "/") + "/" + - name + "/index.html"; - } else if (type === "import") { - displayPath = item.path + "::"; - href = ROOT_PATH + item.path.replace(/::/g, "/") + "/index.html#reexport." + name; - } else if (type === "primitive" || type === "keyword") { - displayPath = ""; - href = ROOT_PATH + path.replace(/::/g, "/") + - "/" + type + "." + name + ".html"; - } else if (type === "externcrate") { - displayPath = ""; - href = ROOT_PATH + name + "/index.html"; - } else if (item.parent !== undefined) { - const myparent = item.parent; - let anchor = type + "." + name; - const parentType = itemTypes[myparent.ty]; - let pageType = parentType; - let pageName = myparent.name; - exactPath = `${myparent.exactPath}::${myparent.name}`; - - if (parentType === "primitive") { - displayPath = myparent.name + "::"; - } else if (type === "structfield" && parentType === "variant") { - // Structfields belonging to variants are special: the - // final path element is the enum name. - const enumNameIdx = item.path.lastIndexOf("::"); - const enumName = item.path.substr(enumNameIdx + 2); - path = item.path.substr(0, enumNameIdx); - displayPath = path + "::" + enumName + "::" + myparent.name + "::"; - anchor = "variant." + myparent.name + ".field." + name; - pageType = "enum"; - pageName = enumName; - } else { - displayPath = path + "::" + myparent.name + "::"; - } - if (item.implDisambiguator !== null) { - anchor = item.implDisambiguator + "/" + anchor; - } - href = ROOT_PATH + path.replace(/::/g, "/") + - "/" + pageType + - "." + pageName + - ".html#" + anchor; - } else { - displayPath = item.path + "::"; - href = ROOT_PATH + item.path.replace(/::/g, "/") + - "/" + type + "." + name + ".html"; - } - return [displayPath, href, `${exactPath}::${name}`]; - } - - function pathSplitter(path) { - const tmp = "<span>" + path.replace(/::/g, "::</span><span>"); - if (tmp.endsWith("<span>")) { - return tmp.slice(0, tmp.length - 6); - } - return tmp; - } - - /** - * Render a set of search results for a single tab. - * @param {Array<?>} array - The search results for this tab - * @param {ParsedQuery} query - * @param {boolean} display - True if this is the active tab - */ - async function addTab(array, query, display) { - const extraClass = display ? " active" : ""; - - const output = document.createElement("div"); - if (array.length > 0) { - output.className = "search-results " + extraClass; - - for (const item of array) { - const name = item.name; - const type = itemTypes[item.ty]; - const longType = longItemTypes[item.ty]; - const typeName = longType.length !== 0 ? `${longType}` : "?"; - - const link = document.createElement("a"); - link.className = "result-" + type; - link.href = item.href; - - const resultName = document.createElement("div"); - resultName.className = "result-name"; - - resultName.insertAdjacentHTML( - "beforeend", - `<span class="typename">${typeName}</span>`); - link.appendChild(resultName); - - let alias = " "; - if (item.is_alias) { - alias = ` <div class="alias">\ -<b>${item.alias}</b><i class="grey"> - see </i>\ -</div>`; - } - resultName.insertAdjacentHTML( - "beforeend", - `<div class="path">${alias}\ -${item.displayPath}<span class="${type}">${name}</span>\ -</div>`); - - const description = document.createElement("div"); - description.className = "desc"; - description.insertAdjacentHTML("beforeend", item.desc); - - link.appendChild(description); - output.appendChild(link); - } - } else if (query.error === null) { - output.className = "search-failed" + extraClass; - output.innerHTML = "No results :(<br/>" + - "Try on <a href=\"https://duckduckgo.com/?q=" + - encodeURIComponent("rust " + query.userQuery) + - "\">DuckDuckGo</a>?<br/><br/>" + - "Or try looking in one of these:<ul><li>The <a " + - "href=\"https://doc.rust-lang.org/reference/index.html\">Rust Reference</a> " + - " for technical details about the language.</li><li><a " + - "href=\"https://doc.rust-lang.org/rust-by-example/index.html\">Rust By " + - "Example</a> for expository code examples.</a></li><li>The <a " + - "href=\"https://doc.rust-lang.org/book/index.html\">Rust Book</a> for " + - "introductions to language features and the language itself.</li><li><a " + - "href=\"https://docs.rs\">Docs.rs</a> for documentation of crates released on" + - " <a href=\"https://crates.io/\">crates.io</a>.</li></ul>"; - } - return [output, array.length]; - } - - function makeTabHeader(tabNb, text, nbElems) { - // https://blog.horizon-eda.org/misc/2020/02/19/ui.html - // - // CSS runs with `font-variant-numeric: tabular-nums` to ensure all - // digits are the same width. \u{2007} is a Unicode space character - // that is defined to be the same width as a digit. - const fmtNbElems = - nbElems < 10 ? `\u{2007}(${nbElems})\u{2007}\u{2007}` : - nbElems < 100 ? `\u{2007}(${nbElems})\u{2007}` : - `\u{2007}(${nbElems})`; - if (searchState.currentTab === tabNb) { - return "<button class=\"selected\">" + text + - "<span class=\"count\">" + fmtNbElems + "</span></button>"; - } - return "<button>" + text + "<span class=\"count\">" + fmtNbElems + "</span></button>"; - } - - /** - * @param {ResultsTable} results - * @param {boolean} go_to_first - * @param {string} filterCrates - */ - async function showResults(results, go_to_first, filterCrates) { - const search = searchState.outputElement(); - if (go_to_first || (results.others.length === 1 - && getSettingValue("go-to-only-result") === "true") - ) { - // Needed to force re-execution of JS when coming back to a page. Let's take this - // scenario as example: - // - // 1. You have the "Directly go to item in search if there is only one result" option - // enabled. - // 2. You make a search which results only one result, leading you automatically to - // this result. - // 3. You go back to previous page. - // - // Now, without the call below, the JS will not be re-executed and the previous state - // will be used, starting search again since the search input is not empty, leading you - // back to the previous page again. - window.onunload = () => {}; - searchState.removeQueryParameters(); - const elem = document.createElement("a"); - elem.href = results.others[0].href; - removeClass(elem, "active"); - // For firefox, we need the element to be in the DOM so it can be clicked. - document.body.appendChild(elem); - elem.click(); - return; - } - if (results.query === undefined) { - results.query = parseQuery(searchState.input.value); - } - - currentResults = results.query.userQuery; +// ==================== Core search logic end ==================== - const [ret_others, ret_in_args, ret_returned] = await Promise.all([ - addTab(results.others, results.query, true), - addTab(results.in_args, results.query, false), - addTab(results.returned, results.query, false), - ]); +let rawSearchIndex; +let docSearch; +const longItemTypes = [ + "keyword", + "primitive type", + "module", + "extern crate", + "re-export", + "struct", + "enum", + "function", + "type alias", + "static", + "trait", + "", + "trait method", + "method", + "struct field", + "enum variant", + "macro", + "assoc type", + "constant", + "assoc const", + "union", + "foreign type", + "existential type", + "attribute macro", + "derive macro", + "trait alias", +]; +let currentResults; - // Navigate to the relevant tab if the current tab is empty, like in case users search - // for "-> String". If they had selected another tab previously, they have to click on - // it again. - let currentTab = searchState.currentTab; - if ((currentTab === 0 && ret_others[1] === 0) || - (currentTab === 1 && ret_in_args[1] === 0) || - (currentTab === 2 && ret_returned[1] === 0)) { - if (ret_others[1] !== 0) { - currentTab = 0; - } else if (ret_in_args[1] !== 0) { - currentTab = 1; - } else if (ret_returned[1] !== 0) { - currentTab = 2; - } - } - - let crates = ""; - if (rawSearchIndex.size > 1) { - crates = " in <div id=\"crate-search-div\"><select id=\"crate-search\">" + - "<option value=\"all crates\">all crates</option>"; - for (const c of rawSearchIndex.keys()) { - crates += `<option value="${c}" ${c === filterCrates && "selected"}>${c}</option>`; - } - crates += "</select></div>"; - } - - let output = `<h1 class="search-results-title">Results${crates}</h1>`; - if (results.query.error !== null) { - const error = results.query.error; - error.forEach((value, index) => { - value = value.split("<").join("<").split(">").join(">"); - if (index % 2 !== 0) { - error[index] = `<code>${value.replaceAll(" ", " ")}</code>`; - } else { - error[index] = value; - } - }); - output += `<h3 class="error">Query parser error: "${error.join("")}".</h3>`; - output += "<div id=\"search-tabs\">" + - makeTabHeader(0, "In Names", ret_others[1]) + - "</div>"; - currentTab = 0; - } else if (results.query.foundElems <= 1 && results.query.returned.length === 0) { - output += "<div id=\"search-tabs\">" + - makeTabHeader(0, "In Names", ret_others[1]) + - makeTabHeader(1, "In Parameters", ret_in_args[1]) + - makeTabHeader(2, "In Return Types", ret_returned[1]) + - "</div>"; +// In the search display, allows to switch between tabs. +function printTab(nb) { + let iter = 0; + let foundCurrentTab = false; + let foundCurrentResultSet = false; + onEachLazy(document.getElementById("search-tabs").childNodes, elem => { + if (nb === iter) { + addClass(elem, "selected"); + foundCurrentTab = true; } else { - const signatureTabTitle = - results.query.elems.length === 0 ? "In Function Return Types" : - results.query.returned.length === 0 ? "In Function Parameters" : - "In Function Signatures"; - output += "<div id=\"search-tabs\">" + - makeTabHeader(0, signatureTabTitle, ret_others[1]) + - "</div>"; - currentTab = 0; + removeClass(elem, "selected"); } - - if (results.query.correction !== null) { - const orig = results.query.returned.length > 0 - ? results.query.returned[0].name - : results.query.elems[0].name; - output += "<h3 class=\"search-corrections\">" + - `Type "${orig}" not found. ` + - "Showing results for closest type name " + - `"${results.query.correction}" instead.</h3>`; - } - if (results.query.proposeCorrectionFrom !== null) { - const orig = results.query.proposeCorrectionFrom; - const targ = results.query.proposeCorrectionTo; - output += "<h3 class=\"search-corrections\">" + - `Type "${orig}" not found and used as generic parameter. ` + - `Consider searching for "${targ}" instead.</h3>`; - } - - const resultsElem = document.createElement("div"); - resultsElem.id = "results"; - resultsElem.appendChild(ret_others[0]); - resultsElem.appendChild(ret_in_args[0]); - resultsElem.appendChild(ret_returned[0]); - - search.innerHTML = output; - const crateSearch = document.getElementById("crate-search"); - if (crateSearch) { - crateSearch.addEventListener("input", updateCrate); - } - search.appendChild(resultsElem); - // Reset focused elements. - searchState.showResults(search); - const elems = document.getElementById("search-tabs").childNodes; - searchState.focusedByTab = []; - let i = 0; - for (const elem of elems) { - const j = i; - elem.onclick = () => printTab(j); - searchState.focusedByTab.push(null); - i += 1; - } - printTab(currentTab); - } - - function updateSearchHistory(url) { - if (!browserSupportsHistoryApi()) { - return; + iter += 1; + }); + const isTypeSearch = (nb > 0 || iter === 1); + iter = 0; + onEachLazy(document.getElementById("results").childNodes, elem => { + if (nb === iter) { + addClass(elem, "active"); + foundCurrentResultSet = true; + } else { + removeClass(elem, "active"); } - const params = searchState.getQueryStringParams(); - if (!history.state && !params.search) { - history.pushState(null, "", url); + iter += 1; + }); + if (foundCurrentTab && foundCurrentResultSet) { + searchState.currentTab = nb; + // Corrections only kick in on type-based searches. + const correctionsElem = document.getElementsByClassName("search-corrections"); + if (isTypeSearch) { + removeClass(correctionsElem[0], "hidden"); } else { - history.replaceState(null, "", url); + addClass(correctionsElem[0], "hidden"); } + } else if (nb !== 0) { + printTab(0); } +} - /** - * Perform a search based on the current state of the search input element - * and display the results. - * @param {boolean} [forced] - */ - async function search(forced) { - const query = parseQuery(searchState.input.value.trim()); - let filterCrates = getFilterCrates(); - - if (!forced && query.userQuery === currentResults) { - if (query.userQuery.length > 0) { - putBackSearch(); - } - return; - } +/** + * Build an URL with search parameters. + * + * @param {string} search - The current search being performed. + * @param {string|null} filterCrates - The current filtering crate (if any). + * + * @return {string} + */ +function buildUrl(search, filterCrates) { + let extra = "?search=" + encodeURIComponent(search); - searchState.setLoadingSearch(); + if (filterCrates !== null) { + extra += "&filter-crate=" + encodeURIComponent(filterCrates); + } + return getNakedUrl() + extra + window.location.hash; +} - const params = searchState.getQueryStringParams(); +/** + * Return the filtering crate or `null` if there is none. + * + * @return {string|null} + */ +function getFilterCrates() { + const elem = document.getElementById("crate-search"); + + if (elem && + elem.value !== "all crates" && + window.searchIndex.has(elem.value) + ) { + return elem.value; + } + return null; +} - // In case we have no information about the saved crate and there is a URL query parameter, - // we override it with the URL query parameter. - if (filterCrates === null && params["filter-crate"] !== undefined) { - filterCrates = params["filter-crate"]; - } +function nextTab(direction) { + const next = (searchState.currentTab + direction + 3) % searchState.focusedByTab.length; + searchState.focusedByTab[searchState.currentTab] = document.activeElement; + printTab(next); + focusSearchResult(); +} - // Update document title to maintain a meaningful browser history - searchState.title = "\"" + query.original + "\" Search - Rust"; +// Focus the first search result on the active tab, or the result that +// was focused last time this tab was active. +function focusSearchResult() { + const target = searchState.focusedByTab[searchState.currentTab] || + document.querySelectorAll(".search-results.active a").item(0) || + document.querySelectorAll("#search-tabs button").item(searchState.currentTab); + searchState.focusedByTab[searchState.currentTab] = null; + if (target) { + target.focus(); + } +} - // Because searching is incremental by character, only the most - // recent search query is added to the browser history. - updateSearchHistory(buildUrl(query.original, filterCrates)); +/** + * Render a set of search results for a single tab. + * @param {Array<?>} array - The search results for this tab + * @param {ParsedQuery} query + * @param {boolean} display - True if this is the active tab + */ +async function addTab(array, query, display) { + const extraClass = display ? " active" : ""; + + const output = document.createElement("div"); + if (array.length > 0) { + output.className = "search-results " + extraClass; + + for (const item of array) { + const name = item.name; + const type = itemTypes[item.ty]; + const longType = longItemTypes[item.ty]; + const typeName = longType.length !== 0 ? `${longType}` : "?"; + + const link = document.createElement("a"); + link.className = "result-" + type; + link.href = item.href; + + const resultName = document.createElement("div"); + resultName.className = "result-name"; + + resultName.insertAdjacentHTML( + "beforeend", + `<span class="typename">${typeName}</span>`); + link.appendChild(resultName); + + let alias = " "; + if (item.is_alias) { + alias = ` <div class="alias">\ +<b>${item.alias}</b><i class="grey"> - see </i>\ +</div>`; + } + resultName.insertAdjacentHTML( + "beforeend", + `<div class="path">${alias}\ +${item.displayPath}<span class="${type}">${name}</span>\ +</div>`); - await showResults( - await execQuery(query, filterCrates, window.currentCrate), - params.go_to_first, - filterCrates); + const description = document.createElement("div"); + description.className = "desc"; + description.insertAdjacentHTML("beforeend", item.desc); + + link.appendChild(description); + output.appendChild(link); + } + } else if (query.error === null) { + output.className = "search-failed" + extraClass; + output.innerHTML = "No results :(<br/>" + + "Try on <a href=\"https://duckduckgo.com/?q=" + + encodeURIComponent("rust " + query.userQuery) + + "\">DuckDuckGo</a>?<br/><br/>" + + "Or try looking in one of these:<ul><li>The <a " + + "href=\"https://doc.rust-lang.org/reference/index.html\">Rust Reference</a> " + + " for technical details about the language.</li><li><a " + + "href=\"https://doc.rust-lang.org/rust-by-example/index.html\">Rust By " + + "Example</a> for expository code examples.</a></li><li>The <a " + + "href=\"https://doc.rust-lang.org/book/index.html\">Rust Book</a> for " + + "introductions to language features and the language itself.</li><li><a " + + "href=\"https://docs.rs\">Docs.rs</a> for documentation of crates released on" + + " <a href=\"https://crates.io/\">crates.io</a>.</li></ul>"; } + return [output, array.length]; +} - /** - * Convert a list of RawFunctionType / ID to object-based FunctionType. - * - * Crates often have lots of functions in them, and it's common to have a large number of - * functions that operate on a small set of data types, so the search index compresses them - * by encoding function parameter and return types as indexes into an array of names. - * - * Even when a general-purpose compression algorithm is used, this is still a win. I checked. - * https://github.com/rust-lang/rust/pull/98475#issue-1284395985 - * - * The format for individual function types is encoded in - * librustdoc/html/render/mod.rs: impl Serialize for RenderType - * - * @param {null|Array<RawFunctionType>} types - * @param {Array<{name: string, ty: number}>} lowercasePaths - * - * @return {Array<FunctionSearchType>} - */ - function buildItemSearchTypeAll(types, lowercasePaths) { - return types.length > 0 ? - types.map(type => buildItemSearchType(type, lowercasePaths)) : - EMPTY_GENERICS_ARRAY; +function makeTabHeader(tabNb, text, nbElems) { + // https://blog.horizon-eda.org/misc/2020/02/19/ui.html + // + // CSS runs with `font-variant-numeric: tabular-nums` to ensure all + // digits are the same width. \u{2007} is a Unicode space character + // that is defined to be the same width as a digit. + const fmtNbElems = + nbElems < 10 ? `\u{2007}(${nbElems})\u{2007}\u{2007}` : + nbElems < 100 ? `\u{2007}(${nbElems})\u{2007}` : `\u{2007}(${nbElems})`; + if (searchState.currentTab === tabNb) { + return "<button class=\"selected\">" + text + + "<span class=\"count\">" + fmtNbElems + "</span></button>"; } + return "<button>" + text + "<span class=\"count\">" + fmtNbElems + "</span></button>"; +} - /** - * Empty, immutable map used in item search types with no bindings. - * - * @type {Map<number, Array<FunctionType>>} - */ - const EMPTY_BINDINGS_MAP = new Map(); - - /** - * Empty, immutable map used in item search types with no bindings. - * - * @type {Array<FunctionType>} - */ - const EMPTY_GENERICS_ARRAY = []; - - /** - * Object pool for function types with no bindings or generics. - * This is reset after loading the index. - * - * @type {Map<number|null, FunctionType>} - */ - let TYPES_POOL = new Map(); +/** + * @param {ResultsTable} results + * @param {boolean} go_to_first + * @param {string} filterCrates + */ +async function showResults(results, go_to_first, filterCrates) { + const search = searchState.outputElement(); + if (go_to_first || (results.others.length === 1 + && getSettingValue("go-to-only-result") === "true") + ) { + // Needed to force re-execution of JS when coming back to a page. Let's take this + // scenario as example: + // + // 1. You have the "Directly go to item in search if there is only one result" option + // enabled. + // 2. You make a search which results only one result, leading you automatically to + // this result. + // 3. You go back to previous page. + // + // Now, without the call below, the JS will not be re-executed and the previous state + // will be used, starting search again since the search input is not empty, leading you + // back to the previous page again. + window.onunload = () => { }; + searchState.removeQueryParameters(); + const elem = document.createElement("a"); + elem.href = results.others[0].href; + removeClass(elem, "active"); + // For firefox, we need the element to be in the DOM so it can be clicked. + document.body.appendChild(elem); + elem.click(); + return; + } + if (results.query === undefined) { + results.query = DocSearch.parseQuery(searchState.input.value); + } - /** - * Converts a single type. - * - * @param {RawFunctionType} type - */ - function buildItemSearchType(type, lowercasePaths, isAssocType) { - const PATH_INDEX_DATA = 0; - const GENERICS_DATA = 1; - const BINDINGS_DATA = 2; - let pathIndex, generics, bindings; - if (typeof type === "number") { - pathIndex = type; - generics = EMPTY_GENERICS_ARRAY; - bindings = EMPTY_BINDINGS_MAP; - } else { - pathIndex = type[PATH_INDEX_DATA]; - generics = buildItemSearchTypeAll( - type[GENERICS_DATA], - lowercasePaths, - ); - if (type.length > BINDINGS_DATA && type[BINDINGS_DATA].length > 0) { - bindings = new Map(type[BINDINGS_DATA].map(binding => { - const [assocType, constraints] = binding; - // Associated type constructors are represented sloppily in rustdoc's - // type search, to make the engine simpler. - // - // MyType<Output<T>=Result<T>> is equivalent to MyType<Output<Result<T>>=T> - // and both are, essentially - // MyType<Output=(T, Result<T>)>, except the tuple isn't actually there. - // It's more like the value of a type binding is naturally an array, - // which rustdoc calls "constraints". - // - // As a result, the key should never have generics on it. - return [ - buildItemSearchType(assocType, lowercasePaths, true).id, - buildItemSearchTypeAll(constraints, lowercasePaths), - ]; - })); - } else { - bindings = EMPTY_BINDINGS_MAP; - } - } - /** - * @type {FunctionType} - */ - let result; - if (pathIndex < 0) { - // types less than 0 are generic parameters - // the actual names of generic parameters aren't stored, since they aren't API - result = { - id: pathIndex, - ty: TY_GENERIC, - path: null, - exactPath: null, - generics, - bindings, - }; - } else if (pathIndex === 0) { - // `0` is used as a sentinel because it's fewer bytes than `null` - result = { - id: null, - ty: null, - path: null, - exactPath: null, - generics, - bindings, - }; - } else { - const item = lowercasePaths[pathIndex - 1]; - result = { - id: buildTypeMapIndex(item.name, isAssocType), - ty: item.ty, - path: item.path, - exactPath: item.exactPath, - generics, - bindings, - }; + currentResults = results.query.userQuery; + + const [ret_others, ret_in_args, ret_returned] = await Promise.all([ + addTab(results.others, results.query, true), + addTab(results.in_args, results.query, false), + addTab(results.returned, results.query, false), + ]); + + // Navigate to the relevant tab if the current tab is empty, like in case users search + // for "-> String". If they had selected another tab previously, they have to click on + // it again. + let currentTab = searchState.currentTab; + if ((currentTab === 0 && ret_others[1] === 0) || + (currentTab === 1 && ret_in_args[1] === 0) || + (currentTab === 2 && ret_returned[1] === 0)) { + if (ret_others[1] !== 0) { + currentTab = 0; + } else if (ret_in_args[1] !== 0) { + currentTab = 1; + } else if (ret_returned[1] !== 0) { + currentTab = 2; } - const cr = TYPES_POOL.get(result.id); - if (cr) { - // Shallow equality check. Since this function is used - // to construct every type object, this should be mostly - // equivalent to a deep equality check, except if there's - // a conflict, we don't keep the old one around, so it's - // not a fully precise implementation of hashcons. - if (cr.generics.length === result.generics.length && - cr.generics !== result.generics && - cr.generics.every((x, i) => result.generics[i] === x) - ) { - result.generics = cr.generics; - } - if (cr.bindings.size === result.bindings.size && cr.bindings !== result.bindings) { - let ok = true; - for (const [k, v] of cr.bindings.entries()) { - const v2 = result.bindings.get(v); - if (!v2) { - ok = false; - break; - } - if (v !== v2 && v.length === v2.length && v.every((x, i) => v2[i] === x)) { - result.bindings.set(k, v); - } else if (v !== v2) { - ok = false; - break; - } - } - if (ok) { - result.bindings = cr.bindings; - } - } - if (cr.ty === result.ty && cr.path === result.path - && cr.bindings === result.bindings && cr.generics === result.generics - && cr.ty === result.ty - ) { - return cr; - } + } + + let crates = ""; + if (rawSearchIndex.size > 1) { + crates = " in <div id=\"crate-search-div\"><select id=\"crate-search\">" + + "<option value=\"all crates\">all crates</option>"; + for (const c of rawSearchIndex.keys()) { + crates += `<option value="${c}" ${c === filterCrates && "selected"}>${c}</option>`; } - TYPES_POOL.set(result.id, result); - return result; + crates += "</select></div>"; } - /** - * Convert from RawFunctionSearchType to FunctionSearchType. - * - * Crates often have lots of functions in them, and function signatures are sometimes complex, - * so rustdoc uses a pretty tight encoding for them. This function converts it to a simpler, - * object-based encoding so that the actual search code is more readable and easier to debug. - * - * The raw function search type format is generated using serde in - * librustdoc/html/render/mod.rs: IndexItemFunctionType::write_to_string - * - * @param {Array<{name: string, ty: number}>} lowercasePaths - * - * @return {null|FunctionSearchType} - */ - function buildFunctionSearchTypeCallback(lowercasePaths) { - return functionSearchType => { - if (functionSearchType === 0) { - return null; - } - const INPUTS_DATA = 0; - const OUTPUT_DATA = 1; - let inputs, output; - if (typeof functionSearchType[INPUTS_DATA] === "number") { - inputs = [buildItemSearchType(functionSearchType[INPUTS_DATA], lowercasePaths)]; + let output = `<h1 class="search-results-title">Results${crates}</h1>`; + if (results.query.error !== null) { + const error = results.query.error; + error.forEach((value, index) => { + value = value.split("<").join("<").split(">").join(">"); + if (index % 2 !== 0) { + error[index] = `<code>${value.replaceAll(" ", " ")}</code>`; } else { - inputs = buildItemSearchTypeAll( - functionSearchType[INPUTS_DATA], - lowercasePaths, - ); + error[index] = value; } - if (functionSearchType.length > 1) { - if (typeof functionSearchType[OUTPUT_DATA] === "number") { - output = [buildItemSearchType(functionSearchType[OUTPUT_DATA], lowercasePaths)]; - } else { - output = buildItemSearchTypeAll( - functionSearchType[OUTPUT_DATA], - lowercasePaths, - ); - } - } else { - output = []; - } - const where_clause = []; - const l = functionSearchType.length; - for (let i = 2; i < l; ++i) { - where_clause.push(typeof functionSearchType[i] === "number" - ? [buildItemSearchType(functionSearchType[i], lowercasePaths)] - : buildItemSearchTypeAll(functionSearchType[i], lowercasePaths)); - } - return { - inputs, output, where_clause, - }; - }; + }); + output += `<h3 class="error">Query parser error: "${error.join("")}".</h3>`; + output += "<div id=\"search-tabs\">" + + makeTabHeader(0, "In Names", ret_others[1]) + + "</div>"; + currentTab = 0; + } else if (results.query.foundElems <= 1 && results.query.returned.length === 0) { + output += "<div id=\"search-tabs\">" + + makeTabHeader(0, "In Names", ret_others[1]) + + makeTabHeader(1, "In Parameters", ret_in_args[1]) + + makeTabHeader(2, "In Return Types", ret_returned[1]) + + "</div>"; + } else { + const signatureTabTitle = + results.query.elems.length === 0 ? "In Function Return Types" : + results.query.returned.length === 0 ? "In Function Parameters" : + "In Function Signatures"; + output += "<div id=\"search-tabs\">" + + makeTabHeader(0, signatureTabTitle, ret_others[1]) + + "</div>"; + currentTab = 0; } - /** - * Type fingerprints allow fast, approximate matching of types. - * - * This algo creates a compact representation of the type set using a Bloom filter. - * This fingerprint is used three ways: - * - * - It accelerates the matching algorithm by checking the function fingerprint against the - * query fingerprint. If any bits are set in the query but not in the function, it can't - * match. - * - * - The fourth section has the number of distinct items in the set. - * This is the distance function, used for filtering and for sorting. - * - * [^1]: Distance is the relatively naive metric of counting the number of distinct items in - * the function that are not present in the query. - * - * @param {FunctionType|QueryElement} type - a single type - * @param {Uint32Array} output - write the fingerprint to this data structure: uses 128 bits - * @param {Set<number>} fps - Set of distinct items - */ - function buildFunctionTypeFingerprint(type, output, fps) { - let input = type.id; - // All forms of `[]`/`()`/`->` get collapsed down to one thing in the bloom filter. - // Differentiating between arrays and slices, if the user asks for it, is - // still done in the matching algorithm. - if (input === typeNameIdOfArray || input === typeNameIdOfSlice) { - input = typeNameIdOfArrayOrSlice; - } - if (input === typeNameIdOfTuple || input === typeNameIdOfUnit) { - input = typeNameIdOfTupleOrUnit; - } - if (input === typeNameIdOfFn || input === typeNameIdOfFnMut || - input === typeNameIdOfFnOnce) { - input = typeNameIdOfHof; - } - // http://burtleburtle.net/bob/hash/integer.html - // ~~ is toInt32. It's used before adding, so - // the number stays in safe integer range. - const hashint1 = k => { - k = (~~k + 0x7ed55d16) + (k << 12); - k = (k ^ 0xc761c23c) ^ (k >>> 19); - k = (~~k + 0x165667b1) + (k << 5); - k = (~~k + 0xd3a2646c) ^ (k << 9); - k = (~~k + 0xfd7046c5) + (k << 3); - return (k ^ 0xb55a4f09) ^ (k >>> 16); - }; - const hashint2 = k => { - k = ~k + (k << 15); - k ^= k >>> 12; - k += k << 2; - k ^= k >>> 4; - k = Math.imul(k, 2057); - return k ^ (k >> 16); - }; - if (input !== null) { - const h0a = hashint1(input); - const h0b = hashint2(input); - // Less Hashing, Same Performance: Building a Better Bloom Filter - // doi=10.1.1.72.2442 - const h1a = ~~(h0a + Math.imul(h0b, 2)); - const h1b = ~~(h0a + Math.imul(h0b, 3)); - const h2a = ~~(h0a + Math.imul(h0b, 4)); - const h2b = ~~(h0a + Math.imul(h0b, 5)); - output[0] |= (1 << (h0a % 32)) | (1 << (h1b % 32)); - output[1] |= (1 << (h1a % 32)) | (1 << (h2b % 32)); - output[2] |= (1 << (h2a % 32)) | (1 << (h0b % 32)); - fps.add(input); - } - for (const g of type.generics) { - buildFunctionTypeFingerprint(g, output, fps); - } - const fb = { - id: null, - ty: 0, - generics: EMPTY_GENERICS_ARRAY, - bindings: EMPTY_BINDINGS_MAP, - }; - for (const [k, v] of type.bindings.entries()) { - fb.id = k; - fb.generics = v; - buildFunctionTypeFingerprint(fb, output, fps); - } - output[3] = fps.size; + if (results.query.correction !== null) { + const orig = results.query.returned.length > 0 + ? results.query.returned[0].name + : results.query.elems[0].name; + output += "<h3 class=\"search-corrections\">" + + `Type "${orig}" not found. ` + + "Showing results for closest type name " + + `"${results.query.correction}" instead.</h3>`; } - - /** - * Compare the query fingerprint with the function fingerprint. - * - * @param {{number}} fullId - The function - * @param {{Uint32Array}} queryFingerprint - The query - * @returns {number|null} - Null if non-match, number if distance - * This function might return 0! - */ - function compareTypeFingerprints(fullId, queryFingerprint) { - const fh0 = functionTypeFingerprint[fullId * 4]; - const fh1 = functionTypeFingerprint[(fullId * 4) + 1]; - const fh2 = functionTypeFingerprint[(fullId * 4) + 2]; - const [qh0, qh1, qh2] = queryFingerprint; - // Approximate set intersection with bloom filters. - // This can be larger than reality, not smaller, because hashes have - // the property that if they've got the same value, they hash to the - // same thing. False positives exist, but not false negatives. - const [in0, in1, in2] = [fh0 & qh0, fh1 & qh1, fh2 & qh2]; - // Approximate the set of items in the query but not the function. - // This might be smaller than reality, but cannot be bigger. - // - // | in_ | qh_ | XOR | Meaning | - // | --- | --- | --- | ------------------------------------------------ | - // | 0 | 0 | 0 | Not present | - // | 1 | 0 | 1 | IMPOSSIBLE because `in_` is `fh_ & qh_` | - // | 1 | 1 | 0 | If one or both is false positive, false negative | - // | 0 | 1 | 1 | Since in_ has no false negatives, must be real | - if ((in0 ^ qh0) || (in1 ^ qh1) || (in2 ^ qh2)) { - return null; - } - return functionTypeFingerprint[(fullId * 4) + 3]; - } - - class VlqHexDecoder { - constructor(string, cons) { - this.string = string; - this.cons = cons; - this.offset = 0; - this.backrefQueue = []; - } - // call after consuming `{` - decodeList() { - let c = this.string.charCodeAt(this.offset); - const ret = []; - while (c !== 125) { // 125 = "}" - ret.push(this.decode()); - c = this.string.charCodeAt(this.offset); - } - this.offset += 1; // eat cb - return ret; - } - // consumes and returns a list or integer - decode() { - let n = 0; - let c = this.string.charCodeAt(this.offset); - if (c === 123) { // 123 = "{" - this.offset += 1; - return this.decodeList(); - } - while (c < 96) { // 96 = "`" - n = (n << 4) | (c & 0xF); - this.offset += 1; - c = this.string.charCodeAt(this.offset); - } - // last character >= la - n = (n << 4) | (c & 0xF); - const [sign, value] = [n & 1, n >> 1]; - this.offset += 1; - return sign ? -value : value; - } - next() { - const c = this.string.charCodeAt(this.offset); - // sixteen characters after "0" are backref - if (c >= 48 && c < 64) { // 48 = "0", 64 = "@" - this.offset += 1; - return this.backrefQueue[c - 48]; - } - // special exception: 0 doesn't use backref encoding - // it's already one character, and it's always nullish - if (c === 96) { // 96 = "`" - this.offset += 1; - return this.cons(0); - } - const result = this.cons(this.decode()); - this.backrefQueue.unshift(result); - if (this.backrefQueue.length > 16) { - this.backrefQueue.pop(); - } - return result; - } - } - class RoaringBitmap { - constructor(str) { - const strdecoded = atob(str); - const u8array = new Uint8Array(strdecoded.length); - for (let j = 0; j < strdecoded.length; ++j) { - u8array[j] = strdecoded.charCodeAt(j); - } - const has_runs = u8array[0] === 0x3b; - const size = has_runs ? - ((u8array[2] | (u8array[3] << 8)) + 1) : - ((u8array[4] | (u8array[5] << 8) | (u8array[6] << 16) | (u8array[7] << 24))); - let i = has_runs ? 4 : 8; - let is_run; - if (has_runs) { - const is_run_len = Math.floor((size + 7) / 8); - is_run = u8array.slice(i, i + is_run_len); - i += is_run_len; - } else { - is_run = new Uint8Array(); - } - this.keys = []; - this.cardinalities = []; - for (let j = 0; j < size; ++j) { - this.keys.push(u8array[i] | (u8array[i + 1] << 8)); - i += 2; - this.cardinalities.push((u8array[i] | (u8array[i + 1] << 8)) + 1); - i += 2; - } - this.containers = []; - let offsets = null; - if (!has_runs || this.keys.length >= 4) { - offsets = []; - for (let j = 0; j < size; ++j) { - offsets.push(u8array[i] | (u8array[i + 1] << 8) | (u8array[i + 2] << 16) | - (u8array[i + 3] << 24)); - i += 4; - } - } - for (let j = 0; j < size; ++j) { - if (offsets && offsets[j] !== i) { - console.log(this.containers); - throw new Error(`corrupt bitmap ${j}: ${i} / ${offsets[j]}`); - } - if (is_run[j >> 3] & (1 << (j & 0x7))) { - const runcount = (u8array[i] | (u8array[i + 1] << 8)); - i += 2; - this.containers.push(new RoaringBitmapRun( - runcount, - u8array.slice(i, i + (runcount * 4)), - )); - i += runcount * 4; - } else if (this.cardinalities[j] >= 4096) { - this.containers.push(new RoaringBitmapBits(u8array.slice(i, i + 8192))); - i += 8192; - } else { - const end = this.cardinalities[j] * 2; - this.containers.push(new RoaringBitmapArray( - this.cardinalities[j], - u8array.slice(i, i + end), - )); - i += end; - } - } - } - contains(keyvalue) { - const key = keyvalue >> 16; - const value = keyvalue & 0xFFFF; - for (let i = 0; i < this.keys.length; ++i) { - if (this.keys[i] === key) { - return this.containers[i].contains(value); - } - } - return false; - } + if (results.query.proposeCorrectionFrom !== null) { + const orig = results.query.proposeCorrectionFrom; + const targ = results.query.proposeCorrectionTo; + output += "<h3 class=\"search-corrections\">" + + `Type "${orig}" not found and used as generic parameter. ` + + `Consider searching for "${targ}" instead.</h3>`; } - class RoaringBitmapRun { - constructor(runcount, array) { - this.runcount = runcount; - this.array = array; - } - contains(value) { - const l = this.runcount * 4; - for (let i = 0; i < l; i += 4) { - const start = this.array[i] | (this.array[i + 1] << 8); - const lenm1 = this.array[i + 2] | (this.array[i + 3] << 8); - if (value >= start && value <= (start + lenm1)) { - return true; - } - } - return false; - } + const resultsElem = document.createElement("div"); + resultsElem.id = "results"; + resultsElem.appendChild(ret_others[0]); + resultsElem.appendChild(ret_in_args[0]); + resultsElem.appendChild(ret_returned[0]); + + search.innerHTML = output; + const crateSearch = document.getElementById("crate-search"); + if (crateSearch) { + crateSearch.addEventListener("input", updateCrate); } - class RoaringBitmapArray { - constructor(cardinality, array) { - this.cardinality = cardinality; - this.array = array; - } - contains(value) { - const l = this.cardinality * 2; - for (let i = 0; i < l; i += 2) { - const start = this.array[i] | (this.array[i + 1] << 8); - if (value === start) { - return true; - } - } - return false; - } + search.appendChild(resultsElem); + // Reset focused elements. + searchState.showResults(search); + const elems = document.getElementById("search-tabs").childNodes; + searchState.focusedByTab = []; + let i = 0; + for (const elem of elems) { + const j = i; + elem.onclick = () => printTab(j); + searchState.focusedByTab.push(null); + i += 1; } - class RoaringBitmapBits { - constructor(array) { - this.array = array; - } - contains(value) { - return !!(this.array[value >> 3] & (1 << (value & 7))); - } + printTab(currentTab); +} + +function updateSearchHistory(url) { + if (!browserSupportsHistoryApi()) { + return; + } + const params = searchState.getQueryStringParams(); + if (!history.state && !params.search) { + history.pushState(null, "", url); + } else { + history.replaceState(null, "", url); } +} - /** - * Convert raw search index into in-memory search index. - * - * @param {[string, RawSearchIndexCrate][]} rawSearchIndex - */ - function buildIndex(rawSearchIndex) { - searchIndex = []; - searchIndexDeprecated = new Map(); - searchIndexEmptyDesc = new Map(); - let currentIndex = 0; - let id = 0; +/** + * Perform a search based on the current state of the search input element + * and display the results. + * @param {boolean} [forced] + */ +async function search(forced) { + const query = DocSearch.parseQuery(searchState.input.value.trim()); + let filterCrates = getFilterCrates(); - // Function type fingerprints are 128-bit bloom filters that are used to - // estimate the distance between function and query. - // This loop counts the number of items to allocate a fingerprint for. - for (const crate of rawSearchIndex.values()) { - // Each item gets an entry in the fingerprint array, and the crate - // does, too - id += crate.t.length + 1; + if (!forced && query.userQuery === currentResults) { + if (query.userQuery.length > 0) { + putBackSearch(); } - functionTypeFingerprint = new Uint32Array((id + 1) * 4); + return; + } - // This loop actually generates the search item indexes, including - // normalized names, type signature objects and fingerprints, and aliases. - id = 0; + searchState.setLoadingSearch(); - for (const [crate, crateCorpus] of rawSearchIndex) { - // a string representing the lengths of each description shard - // a string representing the list of function types - const itemDescShardDecoder = new VlqHexDecoder(crateCorpus.D, noop => noop); - let descShard = { - crate, - shard: 0, - start: 0, - len: itemDescShardDecoder.next(), - promise: null, - resolve: null, - }; - const descShardList = [ descShard ]; - - // Deprecated items and items with no description - searchIndexDeprecated.set(crate, new RoaringBitmap(crateCorpus.c)); - searchIndexEmptyDesc.set(crate, new RoaringBitmap(crateCorpus.e)); - let descIndex = 0; + const params = searchState.getQueryStringParams(); - // This object should have exactly the same set of fields as the "row" - // object defined below. Your JavaScript runtime will thank you. - // https://mathiasbynens.be/notes/shapes-ics - const crateRow = { - crate, - ty: 3, // == ExternCrate - name: crate, - path: "", - descShard, - descIndex, - exactPath: "", - desc: crateCorpus.doc, - parent: undefined, - type: null, - id, - word: crate, - normalizedName: crate.indexOf("_") === -1 ? crate : crate.replace(/_/g, ""), - bitIndex: 0, - implDisambiguator: null, - }; - id += 1; - searchIndex.push(crateRow); - currentIndex += 1; - if (!searchIndexEmptyDesc.get(crate).contains(0)) { - descIndex += 1; - } - - // a String of one character item type codes - const itemTypes = crateCorpus.t; - // an array of (String) item names - const itemNames = crateCorpus.n; - // an array of [(Number) item index, - // (String) full path] - // an item whose index is not present will fall back to the previous present path - // i.e. if indices 4 and 11 are present, but 5-10 and 12-13 are not present, - // 5-10 will fall back to the path for 4 and 12-13 will fall back to the path for 11 - const itemPaths = new Map(crateCorpus.q); - // An array of [(Number) item index, (Number) path index] - // Used to de-duplicate inlined and re-exported stuff - const itemReexports = new Map(crateCorpus.r); - // an array of (Number) the parent path index + 1 to `paths`, or 0 if none - const itemParentIdxDecoder = new VlqHexDecoder(crateCorpus.i, noop => noop); - // a map Number, string for impl disambiguators - const implDisambiguator = new Map(crateCorpus.b); - // an array of [(Number) item type, - // (String) name] - const paths = crateCorpus.p; - // an array of [(String) alias name - // [Number] index to items] - const aliases = crateCorpus.a; + // In case we have no information about the saved crate and there is a URL query parameter, + // we override it with the URL query parameter. + if (filterCrates === null && params["filter-crate"] !== undefined) { + filterCrates = params["filter-crate"]; + } - // an array of [{name: String, ty: Number}] - const lowercasePaths = []; + // Update document title to maintain a meaningful browser history + searchState.title = "\"" + query.original + "\" Search - Rust"; - // a string representing the list of function types - const itemFunctionDecoder = new VlqHexDecoder( - crateCorpus.f, - buildFunctionSearchTypeCallback(lowercasePaths), - ); + // Because searching is incremental by character, only the most + // recent search query is added to the browser history. + updateSearchHistory(buildUrl(query.original, filterCrates)); - // convert `rawPaths` entries into object form - // generate normalizedPaths for function search mode - let len = paths.length; - let lastPath = itemPaths.get(0); - for (let i = 0; i < len; ++i) { - const elem = paths[i]; - const ty = elem[0]; - const name = elem[1]; - let path = null; - if (elem.length > 2) { - path = itemPaths.has(elem[2]) ? itemPaths.get(elem[2]) : lastPath; - lastPath = path; - } - const exactPath = elem.length > 3 ? itemPaths.get(elem[3]) : path; + await showResults( + await docSearch.execQuery(query, filterCrates, window.currentCrate), + params.go_to_first, + filterCrates); +} - lowercasePaths.push({ty, name: name.toLowerCase(), path, exactPath}); - paths[i] = {ty, name, path, exactPath}; - } +/** + * Callback for when the search form is submitted. + * @param {Event} [e] - The event that triggered this call, if any + */ +function onSearchSubmit(e) { + e.preventDefault(); + searchState.clearInputTimeout(); + search(); +} - // convert `item*` into an object form, and construct word indices. - // - // before any analysis is performed lets gather the search terms to - // search against apart from the rest of the data. This is a quick - // operation that is cached for the life of the page state so that - // all other search operations have access to this cached data for - // faster analysis operations - lastPath = ""; - len = itemTypes.length; - let lastName = ""; - let lastWord = ""; - for (let i = 0; i < len; ++i) { - const bitIndex = i + 1; - if (descIndex >= descShard.len && - !searchIndexEmptyDesc.get(crate).contains(bitIndex)) { - descShard = { - crate, - shard: descShard.shard + 1, - start: descShard.start + descShard.len, - len: itemDescShardDecoder.next(), - promise: null, - resolve: null, - }; - descIndex = 0; - descShardList.push(descShard); - } - const name = itemNames[i] === "" ? lastName : itemNames[i]; - const word = itemNames[i] === "" ? lastWord : itemNames[i].toLowerCase(); - const path = itemPaths.has(i) ? itemPaths.get(i) : lastPath; - const type = itemFunctionDecoder.next(); - if (type !== null) { - if (type) { - const fp = functionTypeFingerprint.subarray(id * 4, (id + 1) * 4); - const fps = new Set(); - for (const t of type.inputs) { - buildFunctionTypeFingerprint(t, fp, fps); - } - for (const t of type.output) { - buildFunctionTypeFingerprint(t, fp, fps); - } - for (const w of type.where_clause) { - for (const t of w) { - buildFunctionTypeFingerprint(t, fp, fps); - } - } - } - } - // This object should have exactly the same set of fields as the "crateRow" - // object defined above. - const itemParentIdx = itemParentIdxDecoder.next(); - const row = { - crate, - ty: itemTypes.charCodeAt(i) - 65, // 65 = "A" - name, - path, - descShard, - descIndex, - exactPath: itemReexports.has(i) ? itemPaths.get(itemReexports.get(i)) : path, - parent: itemParentIdx > 0 ? paths[itemParentIdx - 1] : undefined, - type, - id, - word, - normalizedName: word.indexOf("_") === -1 ? word : word.replace(/_/g, ""), - bitIndex, - implDisambiguator: implDisambiguator.has(i) ? implDisambiguator.get(i) : null, - }; - id += 1; - searchIndex.push(row); - lastPath = row.path; - if (!searchIndexEmptyDesc.get(crate).contains(bitIndex)) { - descIndex += 1; - } - lastName = name; - lastWord = word; - } +function putBackSearch() { + const search_input = searchState.input; + if (!searchState.input) { + return; + } + if (search_input.value !== "" && !searchState.isDisplayed()) { + searchState.showResults(); + if (browserSupportsHistoryApi()) { + history.replaceState(null, "", + buildUrl(search_input.value, getFilterCrates())); + } + document.title = searchState.title; + } +} - if (aliases) { - const currentCrateAliases = new Map(); - ALIASES.set(crate, currentCrateAliases); - for (const alias_name in aliases) { - if (!Object.prototype.hasOwnProperty.call(aliases, alias_name)) { - continue; - } +function registerSearchEvents() { + const params = searchState.getQueryStringParams(); - let currentNameAliases; - if (currentCrateAliases.has(alias_name)) { - currentNameAliases = currentCrateAliases.get(alias_name); - } else { - currentNameAliases = []; - currentCrateAliases.set(alias_name, currentNameAliases); - } - for (const local_alias of aliases[alias_name]) { - currentNameAliases.push(local_alias + currentIndex); - } - } - } - currentIndex += itemTypes.length; - searchState.descShards.set(crate, descShardList); - } - // Drop the (rather large) hash table used for reusing function items - TYPES_POOL = new Map(); + // Populate search bar with query string search term when provided, + // but only if the input bar is empty. This avoid the obnoxious issue + // where you start trying to do a search, and the index loads, and + // suddenly your search is gone! + if (searchState.input.value === "") { + searchState.input.value = params.search || ""; } - /** - * Callback for when the search form is submitted. - * @param {Event} [e] - The event that triggered this call, if any - */ - function onSearchSubmit(e) { - e.preventDefault(); + const searchAfter500ms = () => { searchState.clearInputTimeout(); - search(); - } + if (searchState.input.value.length === 0) { + searchState.hideResults(); + } else { + searchState.timeout = setTimeout(search, 500); + } + }; + searchState.input.onkeyup = searchAfter500ms; + searchState.input.oninput = searchAfter500ms; + document.getElementsByClassName("search-form")[0].onsubmit = onSearchSubmit; + searchState.input.onchange = e => { + if (e.target !== document.activeElement) { + // To prevent doing anything when it's from a blur event. + return; + } + // Do NOT e.preventDefault() here. It will prevent pasting. + searchState.clearInputTimeout(); + // zero-timeout necessary here because at the time of event handler execution the + // pasted content is not in the input field yet. Shouldn’t make any difference for + // change, though. + setTimeout(search, 0); + }; + searchState.input.onpaste = searchState.input.onchange; - function putBackSearch() { - const search_input = searchState.input; - if (!searchState.input) { + searchState.outputElement().addEventListener("keydown", e => { + // We only handle unmodified keystrokes here. We don't want to interfere with, + // for instance, alt-left and alt-right for history navigation. + if (e.altKey || e.ctrlKey || e.shiftKey || e.metaKey) { return; } - if (search_input.value !== "" && !searchState.isDisplayed()) { - searchState.showResults(); - if (browserSupportsHistoryApi()) { - history.replaceState(null, "", - buildUrl(search_input.value, getFilterCrates())); - } - document.title = searchState.title; + // up and down arrow select next/previous search result, or the + // search box if we're already at the top. + if (e.which === 38) { // up + const previous = document.activeElement.previousElementSibling; + if (previous) { + previous.focus(); + } else { + searchState.focus(); + } + e.preventDefault(); + } else if (e.which === 40) { // down + const next = document.activeElement.nextElementSibling; + if (next) { + next.focus(); + } + const rect = document.activeElement.getBoundingClientRect(); + if (window.innerHeight - rect.bottom < rect.height) { + window.scrollBy(0, rect.height); + } + e.preventDefault(); + } else if (e.which === 37) { // left + nextTab(-1); + e.preventDefault(); + } else if (e.which === 39) { // right + nextTab(1); + e.preventDefault(); } - } - - function registerSearchEvents() { - const params = searchState.getQueryStringParams(); + }); - // Populate search bar with query string search term when provided, - // but only if the input bar is empty. This avoid the obnoxious issue - // where you start trying to do a search, and the index loads, and - // suddenly your search is gone! - if (searchState.input.value === "") { - searchState.input.value = params.search || ""; + searchState.input.addEventListener("keydown", e => { + if (e.which === 40) { // down + focusSearchResult(); + e.preventDefault(); } + }); - const searchAfter500ms = () => { - searchState.clearInputTimeout(); - if (searchState.input.value.length === 0) { - searchState.hideResults(); - } else { - searchState.timeout = setTimeout(search, 500); - } - }; - searchState.input.onkeyup = searchAfter500ms; - searchState.input.oninput = searchAfter500ms; - document.getElementsByClassName("search-form")[0].onsubmit = onSearchSubmit; - searchState.input.onchange = e => { - if (e.target !== document.activeElement) { - // To prevent doing anything when it's from a blur event. - return; - } - // Do NOT e.preventDefault() here. It will prevent pasting. - searchState.clearInputTimeout(); - // zero-timeout necessary here because at the time of event handler execution the - // pasted content is not in the input field yet. Shouldn’t make any difference for - // change, though. - setTimeout(search, 0); - }; - searchState.input.onpaste = searchState.input.onchange; + searchState.input.addEventListener("focus", () => { + putBackSearch(); + }); - searchState.outputElement().addEventListener("keydown", e => { - // We only handle unmodified keystrokes here. We don't want to interfere with, - // for instance, alt-left and alt-right for history navigation. - if (e.altKey || e.ctrlKey || e.shiftKey || e.metaKey) { - return; - } - // up and down arrow select next/previous search result, or the - // search box if we're already at the top. - if (e.which === 38) { // up - const previous = document.activeElement.previousElementSibling; - if (previous) { - previous.focus(); - } else { - searchState.focus(); - } - e.preventDefault(); - } else if (e.which === 40) { // down - const next = document.activeElement.nextElementSibling; - if (next) { - next.focus(); - } - const rect = document.activeElement.getBoundingClientRect(); - if (window.innerHeight - rect.bottom < rect.height) { - window.scrollBy(0, rect.height); - } - e.preventDefault(); - } else if (e.which === 37) { // left - nextTab(-1); - e.preventDefault(); - } else if (e.which === 39) { // right - nextTab(1); - e.preventDefault(); - } - }); + searchState.input.addEventListener("blur", () => { + searchState.input.placeholder = searchState.input.origPlaceholder; + }); - searchState.input.addEventListener("keydown", e => { - if (e.which === 40) { // down - focusSearchResult(); + // Push and pop states are used to add search results to the browser + // history. + if (browserSupportsHistoryApi()) { + // Store the previous <title> so we can revert back to it later. + const previousTitle = document.title; + + window.addEventListener("popstate", e => { + const params = searchState.getQueryStringParams(); + // Revert to the previous title manually since the History + // API ignores the title parameter. + document.title = previousTitle; + // When browsing forward to search results the previous + // search will be repeated, so the currentResults are + // cleared to ensure the search is successful. + currentResults = null; + // Synchronize search bar with query string state and + // perform the search. This will empty the bar if there's + // nothing there, which lets you really go back to a + // previous state with nothing in the bar. + if (params.search && params.search.length > 0) { + searchState.input.value = params.search; + // Some browsers fire "onpopstate" for every page load + // (Chrome), while others fire the event only when actually + // popping a state (Firefox), which is why search() is + // called both here and at the end of the startSearch() + // function. e.preventDefault(); + search(); + } else { + searchState.input.value = ""; + // When browsing back from search results the main page + // visibility must be reset. + searchState.hideResults(); } }); - - searchState.input.addEventListener("focus", () => { - putBackSearch(); - }); - - searchState.input.addEventListener("blur", () => { - searchState.input.placeholder = searchState.input.origPlaceholder; - }); - - // Push and pop states are used to add search results to the browser - // history. - if (browserSupportsHistoryApi()) { - // Store the previous <title> so we can revert back to it later. - const previousTitle = document.title; - - window.addEventListener("popstate", e => { - const params = searchState.getQueryStringParams(); - // Revert to the previous title manually since the History - // API ignores the title parameter. - document.title = previousTitle; - // When browsing forward to search results the previous - // search will be repeated, so the currentResults are - // cleared to ensure the search is successful. - currentResults = null; - // Synchronize search bar with query string state and - // perform the search. This will empty the bar if there's - // nothing there, which lets you really go back to a - // previous state with nothing in the bar. - if (params.search && params.search.length > 0) { - searchState.input.value = params.search; - // Some browsers fire "onpopstate" for every page load - // (Chrome), while others fire the event only when actually - // popping a state (Firefox), which is why search() is - // called both here and at the end of the startSearch() - // function. - e.preventDefault(); - search(); - } else { - searchState.input.value = ""; - // When browsing back from search results the main page - // visibility must be reset. - searchState.hideResults(); - } - }); - } - - // This is required in firefox to avoid this problem: Navigating to a search result - // with the keyboard, hitting enter, and then hitting back would take you back to - // the doc page, rather than the search that should overlay it. - // This was an interaction between the back-forward cache and our handlers - // that try to sync state between the URL and the search input. To work around it, - // do a small amount of re-init on page show. - window.onpageshow = () => { - const qSearch = searchState.getQueryStringParams().search; - if (searchState.input.value === "" && qSearch) { - searchState.input.value = qSearch; - } - search(); - }; } - function updateCrate(ev) { - if (ev.target.value === "all crates") { - // If we don't remove it from the URL, it'll be picked up again by the search. - const query = searchState.input.value.trim(); - updateSearchHistory(buildUrl(query, null)); + // This is required in firefox to avoid this problem: Navigating to a search result + // with the keyboard, hitting enter, and then hitting back would take you back to + // the doc page, rather than the search that should overlay it. + // This was an interaction between the back-forward cache and our handlers + // that try to sync state between the URL and the search input. To work around it, + // do a small amount of re-init on page show. + window.onpageshow = () => { + const qSearch = searchState.getQueryStringParams().search; + if (searchState.input.value === "" && qSearch) { + searchState.input.value = qSearch; } - // In case you "cut" the entry from the search input, then change the crate filter - // before paste back the previous search, you get the old search results without - // the filter. To prevent this, we need to remove the previous results. - currentResults = null; - search(true); + search(); + }; +} + +function updateCrate(ev) { + if (ev.target.value === "all crates") { + // If we don't remove it from the URL, it'll be picked up again by the search. + const query = searchState.input.value.trim(); + updateSearchHistory(buildUrl(query, null)); } + // In case you "cut" the entry from the search input, then change the crate filter + // before paste back the previous search, you get the old search results without + // the filter. To prevent this, we need to remove the previous results. + currentResults = null; + search(true); +} - buildIndex(rawSearchIndex); +function initSearch(searchIndx) { + rawSearchIndex = searchIndx; if (typeof window !== "undefined") { + docSearch = new DocSearch(rawSearchIndex, ROOT_PATH, searchState); registerSearchEvents(); // If there's a search term in the URL, execute the search now. if (window.searchState.getQueryStringParams().search) { search(); } + } else if (typeof exports !== "undefined") { + docSearch = new DocSearch(rawSearchIndex, ROOT_PATH, searchState); + exports.docSearch = docSearch; + exports.parseQuery = DocSearch.parseQuery; } +} - if (typeof exports !== "undefined") { - exports.initSearch = initSearch; - exports.execQuery = execQuery; - exports.parseQuery = parseQuery; - } +if (typeof exports !== "undefined") { + exports.initSearch = initSearch; } if (typeof window !== "undefined") { @@ -3897,6 +3938,4 @@ if (typeof window !== "undefined") { // exports. initSearch(new Map()); } - - })(); diff --git a/src/tools/clippy/clippy_lints/src/implied_bounds_in_impls.rs b/src/tools/clippy/clippy_lints/src/implied_bounds_in_impls.rs index 67b48878ca5..6794c6cabfe 100644 --- a/src/tools/clippy/clippy_lints/src/implied_bounds_in_impls.rs +++ b/src/tools/clippy/clippy_lints/src/implied_bounds_in_impls.rs @@ -246,7 +246,7 @@ fn collect_supertrait_bounds<'tcx>(cx: &LateContext<'tcx>, bounds: GenericBounds && let [.., path] = poly_trait.trait_ref.path.segments && poly_trait.bound_generic_params.is_empty() && let Some(trait_def_id) = path.res.opt_def_id() - && let predicates = cx.tcx.explicit_super_predicates_of(trait_def_id).predicates + && let predicates = cx.tcx.explicit_super_predicates_of(trait_def_id).skip_binder() // If the trait has no supertrait, there is no need to collect anything from that bound && !predicates.is_empty() { diff --git a/src/tools/clippy/clippy_lints/src/methods/type_id_on_box.rs b/src/tools/clippy/clippy_lints/src/methods/type_id_on_box.rs index b62ecef0069..db8cc4595d4 100644 --- a/src/tools/clippy/clippy_lints/src/methods/type_id_on_box.rs +++ b/src/tools/clippy/clippy_lints/src/methods/type_id_on_box.rs @@ -25,8 +25,7 @@ fn is_subtrait_of_any(cx: &LateContext<'_>, ty: Ty<'_>) -> bool { || cx .tcx .explicit_super_predicates_of(tr.def_id) - .predicates - .iter() + .iter_identity_copied() .any(|(clause, _)| { matches!(clause.kind().skip_binder(), ty::ClauseKind::Trait(super_tr) if cx.tcx.is_diagnostic_item(sym::Any, super_tr.def_id())) diff --git a/src/tools/clippy/clippy_lints/src/needless_maybe_sized.rs b/src/tools/clippy/clippy_lints/src/needless_maybe_sized.rs index a1d8ec3b32e..62e41088f37 100644 --- a/src/tools/clippy/clippy_lints/src/needless_maybe_sized.rs +++ b/src/tools/clippy/clippy_lints/src/needless_maybe_sized.rs @@ -91,7 +91,7 @@ fn path_to_sized_bound(cx: &LateContext<'_>, trait_bound: &PolyTraitRef<'_>) -> return true; } - for &(predicate, _) in cx.tcx.explicit_super_predicates_of(trait_def_id).predicates { + for (predicate, _) in cx.tcx.explicit_super_predicates_of(trait_def_id).iter_identity_copied() { if let ClauseKind::Trait(trait_predicate) = predicate.kind().skip_binder() && trait_predicate.polarity == PredicatePolarity::Positive && !path.contains(&trait_predicate.def_id()) diff --git a/src/tools/miri/src/helpers.rs b/src/tools/miri/src/helpers.rs index 04837456212..a546ad20fef 100644 --- a/src/tools/miri/src/helpers.rs +++ b/src/tools/miri/src/helpers.rs @@ -630,14 +630,11 @@ pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> { self.ecx } - fn aggregate_field_order(memory_index: &IndexVec<FieldIdx, u32>, idx: usize) -> usize { - // We need to do an *inverse* lookup: find the field that has position `idx` in memory order. - for (src_field, &mem_pos) in memory_index.iter_enumerated() { - if mem_pos as usize == idx { - return src_field.as_usize(); - } - } - panic!("invalid `memory_index`, could not find {}-th field in memory order", idx); + fn aggregate_field_iter( + memory_index: &IndexVec<FieldIdx, u32>, + ) -> impl Iterator<Item = FieldIdx> + 'static { + let inverse_memory_index = memory_index.invert_bijective_mapping(); + inverse_memory_index.into_iter() } // Hook to detect `UnsafeCell`. diff --git a/src/tools/rustdoc-js/tester.js b/src/tools/rustdoc-js/tester.js index 43a22f358c3..e162ba033cc 100644 --- a/src/tools/rustdoc-js/tester.js +++ b/src/tools/rustdoc-js/tester.js @@ -427,7 +427,6 @@ function loadSearchJS(doc_folder, resource_suffix) { return list[descIndex]; }, loadedDescShard: function(crate, shard, data) { - //console.log(this.descShards); this.descShards.get(crate)[shard].resolve(data.split("\n")); }, }; @@ -436,15 +435,15 @@ function loadSearchJS(doc_folder, resource_suffix) { const searchJs = fs.readdirSync(staticFiles).find(f => f.match(/search.*\.js$/)); const searchModule = require(path.join(staticFiles, searchJs)); searchModule.initSearch(searchIndex.searchIndex); - + const docSearch = searchModule.docSearch; return { doSearch: function(queryStr, filterCrate, currentCrate) { - return searchModule.execQuery(searchModule.parseQuery(queryStr), + return docSearch.execQuery(searchModule.parseQuery(queryStr), filterCrate, currentCrate); }, getCorrections: function(queryStr, filterCrate, currentCrate) { const parsedQuery = searchModule.parseQuery(queryStr); - searchModule.execQuery(parsedQuery, filterCrate, currentCrate); + docSearch.execQuery(parsedQuery, filterCrate, currentCrate); return parsedQuery.correction; }, parseQuery: searchModule.parseQuery, diff --git a/tests/run-make/native-lib-alt-naming/native.rs b/tests/run-make/native-lib-alt-naming/native.rs new file mode 100644 index 00000000000..6c869e74cd2 --- /dev/null +++ b/tests/run-make/native-lib-alt-naming/native.rs @@ -0,0 +1,2 @@ +#[no_mangle] +pub extern "C" fn native_lib_alt_naming() {} diff --git a/tests/run-make/native-lib-alt-naming/rmake.rs b/tests/run-make/native-lib-alt-naming/rmake.rs new file mode 100644 index 00000000000..d1ea0fc8687 --- /dev/null +++ b/tests/run-make/native-lib-alt-naming/rmake.rs @@ -0,0 +1,15 @@ +// On MSVC the alternative naming format for static libraries (`libfoo.a`) is accepted in addition +// to the default format (`foo.lib`). + +//REMOVE@ only-msvc + +use run_make_support::rustc; + +fn main() { + // Prepare the native library. + rustc().input("native.rs").crate_type("staticlib").output("libnative.a").run(); + + // Try to link to it from both a rlib and a bin. + rustc().input("rust.rs").crate_type("rlib").arg("-lstatic=native").run(); + rustc().input("rust.rs").crate_type("bin").arg("-lstatic=native").run(); +} diff --git a/tests/run-make/native-lib-alt-naming/rust.rs b/tests/run-make/native-lib-alt-naming/rust.rs new file mode 100644 index 00000000000..da0f5d925d1 --- /dev/null +++ b/tests/run-make/native-lib-alt-naming/rust.rs @@ -0,0 +1 @@ +pub fn main() {} diff --git a/tests/rustdoc-json/traits/self.rs b/tests/rustdoc-json/traits/self.rs new file mode 100644 index 00000000000..c7d952ae567 --- /dev/null +++ b/tests/rustdoc-json/traits/self.rs @@ -0,0 +1,58 @@ +// ignore-tidy-linelength + +pub struct Foo; + +// Check that Self is represented uniformly between inherent impls, trait impls, +// and trait definitions, even though it uses both SelfTyParam and SelfTyAlias +// internally. +// +// Each assertion matches 3 times, and should be the same each time. + +impl Foo { + //@ ismany '$.index[*][?(@.name=="by_ref")].inner.function.decl.inputs[0][0]' '"self"' '"self"' '"self"' + //@ ismany '$.index[*][?(@.name=="by_ref")].inner.function.decl.inputs[0][1].borrowed_ref.type.generic' '"Self"' '"Self"' '"Self"' + //@ ismany '$.index[*][?(@.name=="by_ref")].inner.function.decl.inputs[0][1].borrowed_ref.lifetime' null null null + //@ ismany '$.index[*][?(@.name=="by_ref")].inner.function.decl.inputs[0][1].borrowed_ref.mutable' false false false + pub fn by_ref(&self) {} + + //@ ismany '$.index[*][?(@.name=="by_exclusive_ref")].inner.function.decl.inputs[0][0]' '"self"' '"self"' '"self"' + //@ ismany '$.index[*][?(@.name=="by_exclusive_ref")].inner.function.decl.inputs[0][1].borrowed_ref.type.generic' '"Self"' '"Self"' '"Self"' + //@ ismany '$.index[*][?(@.name=="by_exclusive_ref")].inner.function.decl.inputs[0][1].borrowed_ref.lifetime' null null null + //@ ismany '$.index[*][?(@.name=="by_exclusive_ref")].inner.function.decl.inputs[0][1].borrowed_ref.mutable' true true true + pub fn by_exclusive_ref(&mut self) {} + + //@ ismany '$.index[*][?(@.name=="by_value")].inner.function.decl.inputs[0][0]' '"self"' '"self"' '"self"' + //@ ismany '$.index[*][?(@.name=="by_value")].inner.function.decl.inputs[0][1].generic' '"Self"' '"Self"' '"Self"' + pub fn by_value(self) {} + + //@ ismany '$.index[*][?(@.name=="with_lifetime")].inner.function.decl.inputs[0][0]' '"self"' '"self"' '"self"' + //@ ismany '$.index[*][?(@.name=="with_lifetime")].inner.function.decl.inputs[0][1].borrowed_ref.type.generic' '"Self"' '"Self"' '"Self"' + //@ ismany '$.index[*][?(@.name=="with_lifetime")].inner.function.decl.inputs[0][1].borrowed_ref.lifetime' \"\'a\" \"\'a\" \"\'a\" + //@ ismany '$.index[*][?(@.name=="with_lifetime")].inner.function.decl.inputs[0][1].borrowed_ref.mutable' false false false + pub fn with_lifetime<'a>(&'a self) {} + + //@ ismany '$.index[*][?(@.name=="build")].inner.function.decl.output.generic' '"Self"' '"Self"' '"Self"' + pub fn build() -> Self { + Self + } +} + +pub struct Bar; + +pub trait SelfParams { + fn by_ref(&self); + fn by_exclusive_ref(&mut self); + fn by_value(self); + fn with_lifetime<'a>(&'a self); + fn build() -> Self; +} + +impl SelfParams for Bar { + fn by_ref(&self) {} + fn by_exclusive_ref(&mut self) {} + fn by_value(self) {} + fn with_lifetime<'a>(&'a self) {} + fn build() -> Self { + Self + } +} diff --git a/tests/ui/pattern/patterns-dont-match-nt-statement.rs b/tests/ui/pattern/patterns-dont-match-nt-statement.rs new file mode 100644 index 00000000000..c8d41459383 --- /dev/null +++ b/tests/ui/pattern/patterns-dont-match-nt-statement.rs @@ -0,0 +1,19 @@ +//@ check-pass + +// Make sure that a `stmt` nonterminal does not eagerly match against +// a `pat`, since this will always cause a parse error... + +macro_rules! m { + ($pat:pat) => {}; + ($stmt:stmt) => {}; +} + +macro_rules! m2 { + ($stmt:stmt) => { + m! { $stmt } + }; +} + +m2! { let x = 1 } + +fn main() {} |