diff options
52 files changed, 3717 insertions, 504 deletions
diff --git a/Cargo.lock b/Cargo.lock index a93078829e2..49a925d6e37 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -644,9 +644,9 @@ checksum = "55b672471b4e9f9e95499ea597ff64941a309b2cdbffcc46f2cc5e2d971fd335" [[package]] name = "compiler_builtins" -version = "0.1.100" +version = "0.1.101" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d6c0f24437059853f0fa64afc51f338f93647a3de4cf3358ba1bb4171a199775" +checksum = "01a6d58e9c3408138099a396a98fd0d0e6cfb25d723594d2ae48b5004513fd5b" dependencies = [ "cc", "rustc-std-workspace-core", diff --git a/compiler/rustc_hir_typeck/src/fn_ctxt/adjust_fulfillment_errors.rs b/compiler/rustc_hir_typeck/src/fn_ctxt/adjust_fulfillment_errors.rs index 2acb43c51da..43d4496dd48 100644 --- a/compiler/rustc_hir_typeck/src/fn_ctxt/adjust_fulfillment_errors.rs +++ b/compiler/rustc_hir_typeck/src/fn_ctxt/adjust_fulfillment_errors.rs @@ -33,27 +33,17 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { }; let generics = self.tcx.generics_of(def_id); - let predicate_args = match unsubstituted_pred.kind().skip_binder() { - ty::ClauseKind::Trait(pred) => pred.trait_ref.args.to_vec(), - ty::ClauseKind::Projection(pred) => pred.projection_ty.args.to_vec(), - ty::ClauseKind::ConstArgHasType(arg, ty) => { - vec![ty.into(), arg.into()] - } - ty::ClauseKind::ConstEvaluatable(e) => vec![e.into()], - _ => return false, - }; + let (predicate_args, predicate_self_type_to_point_at) = + match unsubstituted_pred.kind().skip_binder() { + ty::ClauseKind::Trait(pred) => { + (pred.trait_ref.args.to_vec(), Some(pred.self_ty().into())) + } + ty::ClauseKind::Projection(pred) => (pred.projection_ty.args.to_vec(), None), + ty::ClauseKind::ConstArgHasType(arg, ty) => (vec![ty.into(), arg.into()], None), + ty::ClauseKind::ConstEvaluatable(e) => (vec![e.into()], None), + _ => return false, + }; - let direct_param = if let ty::ClauseKind::Trait(pred) = unsubstituted_pred.kind().skip_binder() - && let ty = pred.trait_ref.self_ty() - && let ty::Param(_param) = ty.kind() - && let Some(arg) = predicate_args.get(0) - && let ty::GenericArgKind::Type(arg_ty) = arg.unpack() - && arg_ty == ty - { - Some(*arg) - } else { - None - }; let find_param_matching = |matches: &dyn Fn(ty::ParamTerm) -> bool| { predicate_args.iter().find_map(|arg| { arg.walk().find_map(|arg| { @@ -112,18 +102,21 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { let qpath = if let hir::ExprKind::Path(qpath) = expr.kind { Some(qpath) } else { None }; - (Some(*expr), qpath) + (Some(&expr.kind), qpath) } hir::Node::Ty(hir::Ty { kind: hir::TyKind::Path(qpath), .. }) => (None, Some(*qpath)), _ => return false, }; if let Some(qpath) = qpath { - if let Some(param) = direct_param { - if self.point_at_path_if_possible(error, def_id, param, &qpath) { - return true; - } + // Prefer pointing at the turbofished arg that corresponds to the + // self type of the failing predicate over anything else. + if let Some(param) = predicate_self_type_to_point_at + && self.point_at_path_if_possible(error, def_id, param, &qpath) + { + return true; } + if let hir::Node::Expr(hir::Expr { kind: hir::ExprKind::Call(callee, args), hir_id: call_hir_id, @@ -166,11 +159,16 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { } } - match expr.map(|e| e.kind) { + match expr { Some(hir::ExprKind::MethodCall(segment, receiver, args, ..)) => { - if let Some(param) = direct_param + if let Some(param) = predicate_self_type_to_point_at && self.point_at_generic_if_possible(error, def_id, param, segment) { + // HACK: This is not correct, since `predicate_self_type_to_point_at` might + // not actually correspond to the receiver of the method call. But we + // re-adjust the cause code here in order to prefer pointing at one of + // the method's turbofish segments but still use `FunctionArgumentObligation` + // elsewhere. Hopefully this doesn't break something. error.obligation.cause.map_code(|parent_code| { ObligationCauseCode::FunctionArgumentObligation { arg_hir_id: receiver.hir_id, @@ -180,6 +178,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { }); return true; } + for param in [param_to_point_at, fallback_param_to_point_at, self_param_to_point_at] .into_iter() .flatten() @@ -237,7 +236,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { } for param in [ - direct_param, + predicate_self_type_to_point_at, param_to_point_at, fallback_param_to_point_at, self_param_to_point_at, diff --git a/compiler/rustc_hir_typeck/src/fn_ctxt/mod.rs b/compiler/rustc_hir_typeck/src/fn_ctxt/mod.rs index 4237b4488ca..4a245d30c8e 100644 --- a/compiler/rustc_hir_typeck/src/fn_ctxt/mod.rs +++ b/compiler/rustc_hir_typeck/src/fn_ctxt/mod.rs @@ -325,13 +325,16 @@ impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> { fn record_ty(&self, hir_id: hir::HirId, ty: Ty<'tcx>, span: Span) { // FIXME: normalization and escaping regions let ty = if !ty.has_escaping_bound_vars() { - if let ty::Alias( - ty::AliasKind::Projection | ty::AliasKind::Weak, - ty::AliasTy { args, def_id, .. }, - ) = ty.kind() + // NOTE: These obligations are 100% redundant and are implied by + // WF obligations that are registered elsewhere, but they have a + // better cause code assigned to them in `add_required_obligations_for_hir`. + // This means that they should shadow obligations with worse spans. + if let ty::Alias(ty::Projection | ty::Weak, ty::AliasTy { args, def_id, .. }) = + ty.kind() { self.add_required_obligations_for_hir(span, *def_id, args, hir_id); } + self.normalize(span, ty) } else { ty diff --git a/library/panic_abort/src/lib.rs b/library/panic_abort/src/lib.rs index 02534491da9..0dc570b29db 100644 --- a/library/panic_abort/src/lib.rs +++ b/library/panic_abort/src/lib.rs @@ -43,7 +43,8 @@ pub unsafe fn __rust_start_panic(_payload: &mut dyn BoxMeUp) -> u32 { libc::abort(); } } else if #[cfg(any(target_os = "hermit", - all(target_vendor = "fortanix", target_env = "sgx") + all(target_vendor = "fortanix", target_env = "sgx"), + target_os = "xous" ))] { unsafe fn abort() -> ! { // call std::sys::abort_internal diff --git a/library/std/Cargo.toml b/library/std/Cargo.toml index 33c9c6e63c1..e2b97f983d2 100644 --- a/library/std/Cargo.toml +++ b/library/std/Cargo.toml @@ -36,8 +36,8 @@ object = { version = "0.32.0", default-features = false, optional = true, featur rand = { version = "0.8.5", default-features = false, features = ["alloc"] } rand_xorshift = "0.3.0" -[target.'cfg(any(all(target_family = "wasm", target_os = "unknown"), all(target_vendor = "fortanix", target_env = "sgx")))'.dependencies] -dlmalloc = { version = "0.2.3", features = ['rustc-dep-of-std'] } +[target.'cfg(any(all(target_family = "wasm", target_os = "unknown"), target_os = "xous", all(target_vendor = "fortanix", target_env = "sgx")))'.dependencies] +dlmalloc = { version = "0.2.4", features = ['rustc-dep-of-std'] } [target.x86_64-fortanix-unknown-sgx.dependencies] fortanix-sgx-abi = { version = "0.5.0", features = ['rustc-dep-of-std'], public = true } diff --git a/library/std/build.rs b/library/std/build.rs index ddf6e84d8d0..a81c45609ea 100644 --- a/library/std/build.rs +++ b/library/std/build.rs @@ -37,6 +37,7 @@ fn main() { || target.contains("nintendo-3ds") || target.contains("vita") || target.contains("nto") + || target.contains("xous") // See src/bootstrap/synthetic_targets.rs || env::var("RUSTC_BOOTSTRAP_SYNTHETIC_TARGET").is_ok() { diff --git a/library/std/src/fs.rs b/library/std/src/fs.rs index adc1b85fd85..73cce35ac59 100644 --- a/library/std/src/fs.rs +++ b/library/std/src/fs.rs @@ -8,7 +8,7 @@ #![stable(feature = "rust1", since = "1.0.0")] #![deny(unsafe_op_in_unsafe_fn)] -#[cfg(all(test, not(any(target_os = "emscripten", target_env = "sgx"))))] +#[cfg(all(test, not(any(target_os = "emscripten", target_env = "sgx", target_os = "xous"))))] mod tests; use crate::ffi::OsString; diff --git a/library/std/src/lib.rs b/library/std/src/lib.rs index 55c112c7b80..6ec158af94b 100644 --- a/library/std/src/lib.rs +++ b/library/std/src/lib.rs @@ -260,6 +260,7 @@ feature(slice_index_methods, coerce_unsized, sgx_platform) )] #![cfg_attr(windows, feature(round_char_boundary))] +#![cfg_attr(target_os = "xous", feature(slice_ptr_len))] // // Language features: // tidy-alphabetical-start diff --git a/library/std/src/net/tcp.rs b/library/std/src/net/tcp.rs index 32fd54c8e75..9667d5f920e 100644 --- a/library/std/src/net/tcp.rs +++ b/library/std/src/net/tcp.rs @@ -1,6 +1,6 @@ #![deny(unsafe_op_in_unsafe_fn)] -#[cfg(all(test, not(target_os = "emscripten")))] +#[cfg(all(test, not(any(target_os = "emscripten", target_os = "xous"))))] mod tests; use crate::io::prelude::*; diff --git a/library/std/src/net/udp.rs b/library/std/src/net/udp.rs index 5ca4ed832f3..227e418b709 100644 --- a/library/std/src/net/udp.rs +++ b/library/std/src/net/udp.rs @@ -1,4 +1,4 @@ -#[cfg(all(test, not(any(target_os = "emscripten", target_env = "sgx"))))] +#[cfg(all(test, not(any(target_os = "emscripten", target_env = "sgx", target_os = "xous"))))] mod tests; use crate::fmt; diff --git a/library/std/src/os/mod.rs b/library/std/src/os/mod.rs index 634c3cc4a15..de6d784c65b 100644 --- a/library/std/src/os/mod.rs +++ b/library/std/src/os/mod.rs @@ -146,6 +146,8 @@ pub mod vita; pub mod vxworks; #[cfg(target_os = "watchos")] pub(crate) mod watchos; +#[cfg(target_os = "xous")] +pub mod xous; #[cfg(any(unix, target_os = "wasi", doc))] pub mod fd; diff --git a/library/std/src/os/xous/ffi.rs b/library/std/src/os/xous/ffi.rs new file mode 100644 index 00000000000..8be7fbb102f --- /dev/null +++ b/library/std/src/os/xous/ffi.rs @@ -0,0 +1,647 @@ +#![allow(dead_code)] +#![allow(unused_variables)] +#![stable(feature = "rust1", since = "1.0.0")] + +#[path = "../unix/ffi/os_str.rs"] +mod os_str; + +#[stable(feature = "rust1", since = "1.0.0")] +pub use self::os_str::{OsStrExt, OsStringExt}; + +mod definitions; +#[stable(feature = "rust1", since = "1.0.0")] +pub use definitions::*; + +fn lend_mut_impl( + connection: Connection, + opcode: usize, + data: &mut [u8], + arg1: usize, + arg2: usize, + blocking: bool, +) -> Result<(usize, usize), Error> { + let mut a0 = if blocking { Syscall::SendMessage } else { Syscall::TrySendMessage } as usize; + let mut a1: usize = connection.try_into().unwrap(); + let mut a2 = InvokeType::LendMut as usize; + let a3 = opcode; + let a4 = data.as_mut_ptr() as usize; + let a5 = data.len(); + let a6 = arg1; + let a7 = arg2; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::MemoryReturned as usize { + Ok((a1, a2)) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +pub(crate) fn lend_mut( + connection: Connection, + opcode: usize, + data: &mut [u8], + arg1: usize, + arg2: usize, +) -> Result<(usize, usize), Error> { + lend_mut_impl(connection, opcode, data, arg1, arg2, true) +} + +pub(crate) fn try_lend_mut( + connection: Connection, + opcode: usize, + data: &mut [u8], + arg1: usize, + arg2: usize, +) -> Result<(usize, usize), Error> { + lend_mut_impl(connection, opcode, data, arg1, arg2, false) +} + +fn lend_impl( + connection: Connection, + opcode: usize, + data: &[u8], + arg1: usize, + arg2: usize, + blocking: bool, +) -> Result<(usize, usize), Error> { + let mut a0 = if blocking { Syscall::SendMessage } else { Syscall::TrySendMessage } as usize; + let a1: usize = connection.try_into().unwrap(); + let a2 = InvokeType::Lend as usize; + let a3 = opcode; + let a4 = data.as_ptr() as usize; + let a5 = data.len(); + let mut a6 = arg1; + let mut a7 = arg2; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1 => _, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6, + inlateout("a7") a7, + ) + }; + + let result = a0; + + if result == SyscallResult::MemoryReturned as usize { + Ok((a6, a7)) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +pub(crate) fn lend( + connection: Connection, + opcode: usize, + data: &[u8], + arg1: usize, + arg2: usize, +) -> Result<(usize, usize), Error> { + lend_impl(connection, opcode, data, arg1, arg2, true) +} + +pub(crate) fn try_lend( + connection: Connection, + opcode: usize, + data: &[u8], + arg1: usize, + arg2: usize, +) -> Result<(usize, usize), Error> { + lend_impl(connection, opcode, data, arg1, arg2, false) +} + +fn scalar_impl(connection: Connection, args: [usize; 5], blocking: bool) -> Result<(), Error> { + let mut a0 = if blocking { Syscall::SendMessage } else { Syscall::TrySendMessage } as usize; + let mut a1: usize = connection.try_into().unwrap(); + let a2 = InvokeType::Scalar as usize; + let a3 = args[0]; + let a4 = args[1]; + let a5 = args[2]; + let a6 = args[3]; + let a7 = args[4]; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::Ok as usize { + Ok(()) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +pub(crate) fn scalar(connection: Connection, args: [usize; 5]) -> Result<(), Error> { + scalar_impl(connection, args, true) +} + +pub(crate) fn try_scalar(connection: Connection, args: [usize; 5]) -> Result<(), Error> { + scalar_impl(connection, args, false) +} + +fn blocking_scalar_impl( + connection: Connection, + args: [usize; 5], + blocking: bool, +) -> Result<[usize; 5], Error> { + let mut a0 = if blocking { Syscall::SendMessage } else { Syscall::TrySendMessage } as usize; + let mut a1: usize = connection.try_into().unwrap(); + let mut a2 = InvokeType::BlockingScalar as usize; + let mut a3 = args[0]; + let mut a4 = args[1]; + let mut a5 = args[2]; + let a6 = args[3]; + let a7 = args[4]; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2, + inlateout("a3") a3, + inlateout("a4") a4, + inlateout("a5") a5, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::Scalar1 as usize { + Ok([a1, 0, 0, 0, 0]) + } else if result == SyscallResult::Scalar2 as usize { + Ok([a1, a2, 0, 0, 0]) + } else if result == SyscallResult::Scalar5 as usize { + Ok([a1, a2, a3, a4, a5]) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +pub(crate) fn blocking_scalar( + connection: Connection, + args: [usize; 5], +) -> Result<[usize; 5], Error> { + blocking_scalar_impl(connection, args, true) +} + +pub(crate) fn try_blocking_scalar( + connection: Connection, + args: [usize; 5], +) -> Result<[usize; 5], Error> { + blocking_scalar_impl(connection, args, false) +} + +fn connect_impl(address: ServerAddress, blocking: bool) -> Result<Connection, Error> { + let a0 = if blocking { Syscall::Connect } else { Syscall::TryConnect } as usize; + let address: [u32; 4] = address.into(); + let a1: usize = address[0].try_into().unwrap(); + let a2: usize = address[1].try_into().unwrap(); + let a3: usize = address[2].try_into().unwrap(); + let a4: usize = address[3].try_into().unwrap(); + let a5 = 0; + let a6 = 0; + let a7 = 0; + + let mut result: usize; + let mut value: usize; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0 => result, + inlateout("a1") a1 => value, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + if result == SyscallResult::ConnectionId as usize { + Ok(value.try_into().unwrap()) + } else if result == SyscallResult::Error as usize { + Err(value.into()) + } else { + Err(Error::InternalError) + } +} + +/// Connect to a Xous server represented by the specified `address`. +/// +/// The current thread will block until the server is available. Returns +/// an error if the server cannot accept any more connections. +pub(crate) fn connect(address: ServerAddress) -> Result<Connection, Error> { + connect_impl(address, true) +} + +/// Attempt to connect to a Xous server represented by the specified `address`. +/// +/// If the server does not exist then None is returned. +pub(crate) fn try_connect(address: ServerAddress) -> Result<Option<Connection>, Error> { + match connect_impl(address, false) { + Ok(conn) => Ok(Some(conn)), + Err(Error::ServerNotFound) => Ok(None), + Err(e) => Err(e), + } +} + +/// Terminate the current process and return the specified code to the parent process. +pub(crate) fn exit(return_code: u32) -> ! { + let a0 = Syscall::TerminateProcess as usize; + let a1 = return_code as usize; + let a2 = 0; + let a3 = 0; + let a4 = 0; + let a5 = 0; + let a6 = 0; + let a7 = 0; + + unsafe { + core::arch::asm!( + "ecall", + in("a0") a0, + in("a1") a1, + in("a2") a2, + in("a3") a3, + in("a4") a4, + in("a5") a5, + in("a6") a6, + in("a7") a7, + ) + }; + unreachable!(); +} + +/// Suspend the current thread and allow another thread to run. This thread may +/// continue executing again immediately if there are no other threads available +/// to run on the system. +pub(crate) fn do_yield() { + let a0 = Syscall::Yield as usize; + let a1 = 0; + let a2 = 0; + let a3 = 0; + let a4 = 0; + let a5 = 0; + let a6 = 0; + let a7 = 0; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0 => _, + inlateout("a1") a1 => _, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; +} + +/// Allocate memory from the system. An optional physical and/or virtual address +/// may be specified in order to ensure memory is allocated at specific offsets, +/// otherwise the kernel will select an address. +/// +/// # Safety +/// +/// This function is safe unless a virtual address is specified. In that case, +/// the kernel will return an alias to the existing range. This violates Rust's +/// pointer uniqueness guarantee. +pub(crate) unsafe fn map_memory<T>( + phys: Option<core::ptr::NonNull<T>>, + virt: Option<core::ptr::NonNull<T>>, + count: usize, + flags: MemoryFlags, +) -> Result<&'static mut [T], Error> { + let mut a0 = Syscall::MapMemory as usize; + let mut a1 = phys.map(|p| p.as_ptr() as usize).unwrap_or_default(); + let mut a2 = virt.map(|p| p.as_ptr() as usize).unwrap_or_default(); + let a3 = count * core::mem::size_of::<T>(); + let a4 = flags.bits(); + let a5 = 0; + let a6 = 0; + let a7 = 0; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::MemoryRange as usize { + let start = core::ptr::from_exposed_addr_mut::<T>(a1); + let len = a2 / core::mem::size_of::<T>(); + let end = unsafe { start.add(len) }; + Ok(unsafe { core::slice::from_raw_parts_mut(start, len) }) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +/// Destroy the given memory, returning it to the compiler. +/// +/// Safety: The memory pointed to by `range` should not be used after this +/// function returns, even if this function returns Err(). +pub(crate) unsafe fn unmap_memory<T>(range: *mut [T]) -> Result<(), Error> { + let mut a0 = Syscall::UnmapMemory as usize; + let mut a1 = range.as_mut_ptr() as usize; + let a2 = range.len(); + let a3 = 0; + let a4 = 0; + let a5 = 0; + let a6 = 0; + let a7 = 0; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::Ok as usize { + Ok(()) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +/// Adjust the memory flags for the given range. This can be used to remove flags +/// from a given region in order to harden memory access. Note that flags may +/// only be removed and may never be added. +/// +/// Safety: The memory pointed to by `range` may become inaccessible or have its +/// mutability removed. It is up to the caller to ensure that the flags specified +/// by `new_flags` are upheld, otherwise the program will crash. +pub(crate) unsafe fn update_memory_flags<T>( + range: *mut [T], + new_flags: MemoryFlags, +) -> Result<(), Error> { + let mut a0 = Syscall::UpdateMemoryFlags as usize; + let mut a1 = range.as_mut_ptr() as usize; + let a2 = range.len(); + let a3 = new_flags.bits(); + let a4 = 0; // Process ID is currently None + let a5 = 0; + let a6 = 0; + let a7 = 0; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::Ok as usize { + Ok(()) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +/// Create a thread with a given stack and up to four arguments +pub(crate) fn create_thread( + start: *mut usize, + stack: *mut [u8], + arg0: usize, + arg1: usize, + arg2: usize, + arg3: usize, +) -> Result<ThreadId, Error> { + let mut a0 = Syscall::CreateThread as usize; + let mut a1 = start as usize; + let a2 = stack.as_mut_ptr() as usize; + let a3 = stack.len(); + let a4 = arg0; + let a5 = arg1; + let a6 = arg2; + let a7 = arg3; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::ThreadId as usize { + Ok(a1.into()) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +/// Wait for the given thread to terminate and return the exit code from that thread. +pub(crate) fn join_thread(thread_id: ThreadId) -> Result<usize, Error> { + let mut a0 = Syscall::JoinThread as usize; + let mut a1 = thread_id.into(); + let a2 = 0; + let a3 = 0; + let a4 = 0; + let a5 = 0; + let a6 = 0; + let a7 = 0; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::Scalar1 as usize { + Ok(a1) + } else if result == SyscallResult::Scalar2 as usize { + Ok(a1) + } else if result == SyscallResult::Scalar5 as usize { + Ok(a1) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +/// Get the current thread's ID +pub(crate) fn thread_id() -> Result<ThreadId, Error> { + let mut a0 = Syscall::GetThreadId as usize; + let mut a1 = 0; + let a2 = 0; + let a3 = 0; + let a4 = 0; + let a5 = 0; + let a6 = 0; + let a7 = 0; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::ThreadId as usize { + Ok(a1.into()) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} + +/// Adjust the given `knob` limit to match the new value `new`. The current value must +/// match the `current` in order for this to take effect. +/// +/// The new value is returned as a result of this call. If the call fails, then the old +/// value is returned. In either case, this function returns successfully. +/// +/// An error is generated if the `knob` is not a valid limit, or if the call +/// would not succeed. +pub(crate) fn adjust_limit(knob: Limits, current: usize, new: usize) -> Result<usize, Error> { + let mut a0 = Syscall::JoinThread as usize; + let mut a1 = knob as usize; + let a2 = current; + let a3 = new; + let a4 = 0; + let a5 = 0; + let a6 = 0; + let a7 = 0; + + unsafe { + core::arch::asm!( + "ecall", + inlateout("a0") a0, + inlateout("a1") a1, + inlateout("a2") a2 => _, + inlateout("a3") a3 => _, + inlateout("a4") a4 => _, + inlateout("a5") a5 => _, + inlateout("a6") a6 => _, + inlateout("a7") a7 => _, + ) + }; + + let result = a0; + + if result == SyscallResult::Scalar2 as usize && a1 == knob as usize { + Ok(a2) + } else if result == SyscallResult::Scalar5 as usize && a1 == knob as usize { + Ok(a1) + } else if result == SyscallResult::Error as usize { + Err(a1.into()) + } else { + Err(Error::InternalError) + } +} diff --git a/library/std/src/os/xous/ffi/definitions.rs b/library/std/src/os/xous/ffi/definitions.rs new file mode 100644 index 00000000000..345005bcc78 --- /dev/null +++ b/library/std/src/os/xous/ffi/definitions.rs @@ -0,0 +1,283 @@ +mod memoryflags; +pub(crate) use memoryflags::*; + +#[stable(feature = "rust1", since = "1.0.0")] +/// Indicates a particular syscall number as used by the Xous kernel. +#[derive(Copy, Clone)] +#[repr(usize)] +pub enum Syscall { + MapMemory = 2, + Yield = 3, + UpdateMemoryFlags = 12, + ReceiveMessage = 15, + SendMessage = 16, + Connect = 17, + CreateThread = 18, + UnmapMemory = 19, + ReturnMemory = 20, + TerminateProcess = 22, + TrySendMessage = 24, + TryConnect = 25, + GetThreadId = 32, + JoinThread = 36, + AdjustProcessLimit = 38, + ReturnScalar = 40, +} + +#[stable(feature = "rust1", since = "1.0.0")] +/// Copies of these invocation types here for when we're running +/// in environments without libxous. +#[derive(Copy, Clone)] +#[repr(usize)] +pub enum SyscallResult { + Ok = 0, + Error = 1, + MemoryRange = 3, + ConnectionId = 7, + Message = 9, + ThreadId = 10, + Scalar1 = 14, + Scalar2 = 15, + MemoryReturned = 18, + Scalar5 = 20, +} + +#[stable(feature = "rust1", since = "1.0.0")] +#[derive(Copy, Clone)] +/// A list of all known errors that may be returned by the Xous kernel. +#[repr(usize)] +pub enum Error { + NoError = 0, + BadAlignment = 1, + BadAddress = 2, + OutOfMemory = 3, + MemoryInUse = 4, + InterruptNotFound = 5, + InterruptInUse = 6, + InvalidString = 7, + ServerExists = 8, + ServerNotFound = 9, + ProcessNotFound = 10, + ProcessNotChild = 11, + ProcessTerminated = 12, + Timeout = 13, + InternalError = 14, + ServerQueueFull = 15, + ThreadNotAvailable = 16, + UnhandledSyscall = 17, + InvalidSyscall = 18, + ShareViolation = 19, + InvalidThread = 20, + InvalidPid = 21, + UnknownError = 22, + AccessDenied = 23, + UseBeforeInit = 24, + DoubleFree = 25, + DebugInProgress = 26, + InvalidLimit = 27, +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl From<usize> for Error { + fn from(src: usize) -> Self { + match src { + 0 => Self::NoError, + 1 => Self::BadAlignment, + 2 => Self::BadAddress, + 3 => Self::OutOfMemory, + 4 => Self::MemoryInUse, + 5 => Self::InterruptNotFound, + 6 => Self::InterruptInUse, + 7 => Self::InvalidString, + 8 => Self::ServerExists, + 9 => Self::ServerNotFound, + 10 => Self::ProcessNotFound, + 11 => Self::ProcessNotChild, + 12 => Self::ProcessTerminated, + 13 => Self::Timeout, + 14 => Self::InternalError, + 15 => Self::ServerQueueFull, + 16 => Self::ThreadNotAvailable, + 17 => Self::UnhandledSyscall, + 18 => Self::InvalidSyscall, + 19 => Self::ShareViolation, + 20 => Self::InvalidThread, + 21 => Self::InvalidPid, + 23 => Self::AccessDenied, + 24 => Self::UseBeforeInit, + 25 => Self::DoubleFree, + 26 => Self::DebugInProgress, + 27 => Self::InvalidLimit, + 22 | _ => Self::UnknownError, + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl From<i32> for Error { + fn from(src: i32) -> Self { + let Ok(src) = core::convert::TryInto::<usize>::try_into(src) else { + return Self::UnknownError; + }; + src.into() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::fmt::Display for Error { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + write!( + f, + "{}", + match self { + Error::NoError => "no error occurred", + Error::BadAlignment => "memory was not properly aligned", + Error::BadAddress => "an invalid address was supplied", + Error::OutOfMemory => "the process or service has run out of memory", + Error::MemoryInUse => "the requested address is in use", + Error::InterruptNotFound => + "the requested interrupt does not exist on this platform", + Error::InterruptInUse => "the requested interrupt is currently in use", + Error::InvalidString => "the specified string was not formatted correctly", + Error::ServerExists => "a server with that address already exists", + Error::ServerNotFound => "the requetsed server could not be found", + Error::ProcessNotFound => "the target process does not exist", + Error::ProcessNotChild => + "the requested operation can only be done on child processes", + Error::ProcessTerminated => "the target process has crashed", + Error::Timeout => "the requested operation timed out", + Error::InternalError => "an internal error occurred", + Error::ServerQueueFull => "the server has too many pending messages", + Error::ThreadNotAvailable => "the specified thread does not exist", + Error::UnhandledSyscall => "the kernel did not recognize that syscall", + Error::InvalidSyscall => "the syscall had incorrect parameters", + Error::ShareViolation => "an attempt was made to share memory twice", + Error::InvalidThread => "tried to resume a thread that was not ready", + Error::InvalidPid => "kernel attempted to use a pid that was not valid", + Error::AccessDenied => "no permission to perform the requested operation", + Error::UseBeforeInit => "attempt to use a service before initialization finished", + Error::DoubleFree => "the requested resource was freed twice", + Error::DebugInProgress => "kernel attempted to activate a thread being debugged", + Error::InvalidLimit => "process attempted to adjust an invalid limit", + Error::UnknownError => "an unknown error occurred", + } + ) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::fmt::Debug for Error { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + write!(f, "{}", self) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl crate::error::Error for Error {} + +/// Indicates the type of Message that is sent when making a `SendMessage` syscall. +#[derive(Copy, Clone)] +#[repr(usize)] +pub(crate) enum InvokeType { + LendMut = 1, + Lend = 2, + Move = 3, + Scalar = 4, + BlockingScalar = 5, +} + +#[stable(feature = "rust1", since = "1.0.0")] +#[derive(Debug, Copy, Clone)] +/// A representation of a connection to a Xous service. +pub struct Connection(u32); + +#[stable(feature = "rust1", since = "1.0.0")] +impl From<u32> for Connection { + fn from(src: u32) -> Connection { + Connection(src) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl TryFrom<usize> for Connection { + type Error = core::num::TryFromIntError; + fn try_from(src: usize) -> Result<Self, Self::Error> { + Ok(Connection(src.try_into()?)) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Into<u32> for Connection { + fn into(self) -> u32 { + self.0 + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl TryInto<usize> for Connection { + type Error = core::num::TryFromIntError; + fn try_into(self) -> Result<usize, Self::Error> { + self.0.try_into() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +#[derive(Debug)] +pub enum ServerAddressError { + InvalidLength, +} + +#[stable(feature = "rust1", since = "1.0.0")] +pub struct ServerAddress([u32; 4]); + +#[stable(feature = "rust1", since = "1.0.0")] +impl TryFrom<&str> for ServerAddress { + type Error = ServerAddressError; + fn try_from(value: &str) -> Result<Self, Self::Error> { + let b = value.as_bytes(); + if b.len() == 0 || b.len() > 16 { + return Err(Self::Error::InvalidLength); + } + + let mut this_temp = [0u8; 16]; + for (dest, src) in this_temp.iter_mut().zip(b.iter()) { + *dest = *src; + } + + let mut this = [0u32; 4]; + for (dest, src) in this.iter_mut().zip(this_temp.chunks_exact(4)) { + *dest = u32::from_le_bytes(src.try_into().unwrap()); + } + Ok(ServerAddress(this)) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Into<[u32; 4]> for ServerAddress { + fn into(self) -> [u32; 4] { + self.0 + } +} + +#[derive(Debug, Copy, Clone)] +pub(crate) struct ThreadId(usize); + +impl From<usize> for ThreadId { + fn from(src: usize) -> ThreadId { + ThreadId(src) + } +} + +impl Into<usize> for ThreadId { + fn into(self) -> usize { + self.0 + } +} + +#[derive(Copy, Clone)] +#[repr(usize)] +/// Limits that can be passed to `AdjustLimit` +pub(crate) enum Limits { + HeapMaximum = 1, + HeapSize = 2, +} diff --git a/library/std/src/os/xous/ffi/definitions/memoryflags.rs b/library/std/src/os/xous/ffi/definitions/memoryflags.rs new file mode 100644 index 00000000000..af9de3cbff2 --- /dev/null +++ b/library/std/src/os/xous/ffi/definitions/memoryflags.rs @@ -0,0 +1,176 @@ +/// Flags to be passed to the MapMemory struct. +/// Note that it is an error to have memory be +/// writable and not readable. +#[derive(Copy, PartialEq, Eq, Clone, PartialOrd, Ord, Hash, Debug)] +#[stable(feature = "rust1", since = "1.0.0")] +pub struct MemoryFlags { + bits: usize, +} + +impl MemoryFlags { + /// Free this memory + #[stable(feature = "rust1", since = "1.0.0")] + pub const FREE: Self = Self { bits: 0b0000_0000 }; + + /// Immediately allocate this memory. Otherwise it will + /// be demand-paged. This is implicitly set when `phys` + /// is not 0. + #[stable(feature = "rust1", since = "1.0.0")] + pub const RESERVE: Self = Self { bits: 0b0000_0001 }; + + /// Allow the CPU to read from this page. + #[stable(feature = "rust1", since = "1.0.0")] + pub const R: Self = Self { bits: 0b0000_0010 }; + + /// Allow the CPU to write to this page. + #[stable(feature = "rust1", since = "1.0.0")] + pub const W: Self = Self { bits: 0b0000_0100 }; + + /// Allow the CPU to execute from this page. + #[stable(feature = "rust1", since = "1.0.0")] + pub const X: Self = Self { bits: 0b0000_1000 }; + + #[stable(feature = "rust1", since = "1.0.0")] + pub fn bits(&self) -> usize { + self.bits + } + + #[stable(feature = "rust1", since = "1.0.0")] + pub fn from_bits(raw: usize) -> Option<MemoryFlags> { + if raw > 16 { None } else { Some(MemoryFlags { bits: raw }) } + } + + #[stable(feature = "rust1", since = "1.0.0")] + pub fn is_empty(&self) -> bool { + self.bits == 0 + } + + #[stable(feature = "rust1", since = "1.0.0")] + pub fn empty() -> MemoryFlags { + MemoryFlags { bits: 0 } + } + + #[stable(feature = "rust1", since = "1.0.0")] + pub fn all() -> MemoryFlags { + MemoryFlags { bits: 15 } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::fmt::Binary for MemoryFlags { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + core::fmt::Binary::fmt(&self.bits, f) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::fmt::Octal for MemoryFlags { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + core::fmt::Octal::fmt(&self.bits, f) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::fmt::LowerHex for MemoryFlags { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + core::fmt::LowerHex::fmt(&self.bits, f) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::fmt::UpperHex for MemoryFlags { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + core::fmt::UpperHex::fmt(&self.bits, f) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::ops::BitOr for MemoryFlags { + type Output = Self; + + /// Returns the union of the two sets of flags. + #[inline] + fn bitor(self, other: MemoryFlags) -> Self { + Self { bits: self.bits | other.bits } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::ops::BitOrAssign for MemoryFlags { + /// Adds the set of flags. + #[inline] + fn bitor_assign(&mut self, other: Self) { + self.bits |= other.bits; + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::ops::BitXor for MemoryFlags { + type Output = Self; + + /// Returns the left flags, but with all the right flags toggled. + #[inline] + fn bitxor(self, other: Self) -> Self { + Self { bits: self.bits ^ other.bits } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::ops::BitXorAssign for MemoryFlags { + /// Toggles the set of flags. + #[inline] + fn bitxor_assign(&mut self, other: Self) { + self.bits ^= other.bits; + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::ops::BitAnd for MemoryFlags { + type Output = Self; + + /// Returns the intersection between the two sets of flags. + #[inline] + fn bitand(self, other: Self) -> Self { + Self { bits: self.bits & other.bits } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::ops::BitAndAssign for MemoryFlags { + /// Disables all flags disabled in the set. + #[inline] + fn bitand_assign(&mut self, other: Self) { + self.bits &= other.bits; + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::ops::Sub for MemoryFlags { + type Output = Self; + + /// Returns the set difference of the two sets of flags. + #[inline] + fn sub(self, other: Self) -> Self { + Self { bits: self.bits & !other.bits } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::ops::SubAssign for MemoryFlags { + /// Disables all flags enabled in the set. + #[inline] + fn sub_assign(&mut self, other: Self) { + self.bits &= !other.bits; + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::ops::Not for MemoryFlags { + type Output = Self; + + /// Returns the complement of this set of flags. + #[inline] + fn not(self) -> Self { + Self { bits: !self.bits } & MemoryFlags { bits: 15 } + } +} diff --git a/library/std/src/os/xous/mod.rs b/library/std/src/os/xous/mod.rs new file mode 100644 index 00000000000..153694a89a7 --- /dev/null +++ b/library/std/src/os/xous/mod.rs @@ -0,0 +1,17 @@ +#![stable(feature = "rust1", since = "1.0.0")] +#![doc(cfg(target_os = "xous"))] + +pub mod ffi; + +#[stable(feature = "rust1", since = "1.0.0")] +pub mod services; + +/// A prelude for conveniently writing platform-specific code. +/// +/// Includes all extension traits, and some important type definitions. +#[stable(feature = "rust1", since = "1.0.0")] +pub mod prelude { + #[doc(no_inline)] + #[stable(feature = "rust1", since = "1.0.0")] + pub use super::ffi::{OsStrExt, OsStringExt}; +} diff --git a/library/std/src/os/xous/services.rs b/library/std/src/os/xous/services.rs new file mode 100644 index 00000000000..5c219f1fbb9 --- /dev/null +++ b/library/std/src/os/xous/services.rs @@ -0,0 +1,132 @@ +use crate::os::xous::ffi::Connection; +use core::sync::atomic::{AtomicU32, Ordering}; + +mod log; +pub(crate) use log::*; + +mod systime; +pub(crate) use systime::*; + +mod ticktimer; +pub(crate) use ticktimer::*; + +mod ns { + const NAME_MAX_LENGTH: usize = 64; + use crate::os::xous::ffi::{lend_mut, Connection}; + // By making this repr(C), the layout of this struct becomes well-defined + // and no longer shifts around. + // By marking it as `align(4096)` we define that it will be page-aligned, + // meaning it can be sent between processes. We make sure to pad out the + // entire struct so that memory isn't leaked to the name server. + #[repr(C, align(4096))] + struct ConnectRequest { + data: [u8; 4096], + } + + impl ConnectRequest { + pub fn new(name: &str) -> Self { + let mut cr = ConnectRequest { data: [0u8; 4096] }; + let name_bytes = name.as_bytes(); + + // Copy the string into our backing store. + for (&src_byte, dest_byte) in name_bytes.iter().zip(&mut cr.data[0..NAME_MAX_LENGTH]) { + *dest_byte = src_byte; + } + + // Set the string length to the length of the passed-in String, + // or the maximum possible length. Which ever is smaller. + for (&src_byte, dest_byte) in (name.len().min(NAME_MAX_LENGTH) as u32) + .to_le_bytes() + .iter() + .zip(&mut cr.data[NAME_MAX_LENGTH..]) + { + *dest_byte = src_byte; + } + cr + } + } + + pub fn connect_with_name_impl(name: &str, blocking: bool) -> Option<Connection> { + let mut request = ConnectRequest::new(name); + let opcode = if blocking { + 6 /* BlockingConnect */ + } else { + 7 /* TryConnect */ + }; + let cid = if blocking { super::name_server() } else { super::try_name_server()? }; + + lend_mut(cid, opcode, &mut request.data, 0, name.len().min(NAME_MAX_LENGTH)) + .expect("unable to perform lookup"); + + // Read the result code back from the nameserver + let result = u32::from_le_bytes(request.data[0..4].try_into().unwrap()); + if result == 0 { + // If the result was successful, then the CID is stored in the next 4 bytes + Some(u32::from_le_bytes(request.data[4..8].try_into().unwrap()).into()) + } else { + None + } + } + + pub fn connect_with_name(name: &str) -> Option<Connection> { + connect_with_name_impl(name, true) + } + + pub fn try_connect_with_name(name: &str) -> Option<Connection> { + connect_with_name_impl(name, false) + } +} + +/// Attempt to connect to a server by name. If the server does not exist, this will +/// block until the server is created. +/// +/// Note that this is different from connecting to a server by address. Server +/// addresses are always 16 bytes long, whereas server names are arbitrary-length +/// strings up to 64 bytes in length. +#[stable(feature = "rust1", since = "1.0.0")] +pub fn connect(name: &str) -> Option<Connection> { + ns::connect_with_name(name) +} + +/// Attempt to connect to a server by name. If the server does not exist, this will +/// immediately return `None`. +/// +/// Note that this is different from connecting to a server by address. Server +/// addresses are always 16 bytes long, whereas server names are arbitrary-length +/// strings. +#[stable(feature = "rust1", since = "1.0.0")] +pub fn try_connect(name: &str) -> Option<Connection> { + ns::try_connect_with_name(name) +} + +static NAME_SERVER_CONNECTION: AtomicU32 = AtomicU32::new(0); + +/// Return a `Connection` to the name server. If the name server has not been started, +/// then this call will block until the name server has been started. The `Connection` +/// will be shared among all connections in a process, so it is safe to call this +/// multiple times. +pub(crate) fn name_server() -> Connection { + let cid = NAME_SERVER_CONNECTION.load(Ordering::Relaxed); + if cid != 0 { + return cid.into(); + } + + let cid = crate::os::xous::ffi::connect("xous-name-server".try_into().unwrap()).unwrap(); + NAME_SERVER_CONNECTION.store(cid.into(), Ordering::Relaxed); + cid +} + +fn try_name_server() -> Option<Connection> { + let cid = NAME_SERVER_CONNECTION.load(Ordering::Relaxed); + if cid != 0 { + return Some(cid.into()); + } + + if let Ok(Some(cid)) = crate::os::xous::ffi::try_connect("xous-name-server".try_into().unwrap()) + { + NAME_SERVER_CONNECTION.store(cid.into(), Ordering::Relaxed); + Some(cid) + } else { + None + } +} diff --git a/library/std/src/os/xous/services/log.rs b/library/std/src/os/xous/services/log.rs new file mode 100644 index 00000000000..e6bae929eac --- /dev/null +++ b/library/std/src/os/xous/services/log.rs @@ -0,0 +1,63 @@ +use crate::os::xous::ffi::Connection; +use core::sync::atomic::{AtomicU32, Ordering}; + +/// Group `usize` bytes into a `usize` and return it, beginning +/// from `offset` * sizeof(usize) bytes from the start. For example, +/// `group_or_null([1,2,3,4,5,6,7,8], 1)` on a 32-bit system will +/// return a usize with 5678 packed into it. +fn group_or_null(data: &[u8], offset: usize) -> usize { + let start = offset * core::mem::size_of::<usize>(); + let mut out_array = [0u8; core::mem::size_of::<usize>()]; + if start < data.len() { + for (dest, src) in out_array.iter_mut().zip(&data[start..]) { + *dest = *src; + } + } + usize::from_le_bytes(out_array) +} + +pub(crate) enum LogScalar<'a> { + /// A panic occurred, and a panic log is forthcoming + BeginPanic, + + /// Some number of bytes will be appended to the log message + AppendPanicMessage(&'a [u8]), +} + +impl<'a> Into<[usize; 5]> for LogScalar<'a> { + fn into(self) -> [usize; 5] { + match self { + LogScalar::BeginPanic => [1000, 0, 0, 0, 0], + LogScalar::AppendPanicMessage(c) => + // Text is grouped into 4x `usize` words. The id is 1100 plus + // the number of characters in this message. + // Ignore errors since we're already panicking. + { + [ + 1100 + c.len(), + group_or_null(&c, 0), + group_or_null(&c, 1), + group_or_null(&c, 2), + group_or_null(&c, 3), + ] + } + } + } +} + +/// Return a `Connection` to the log server, which is used for printing messages to +/// the console and reporting panics. If the log server has not yet started, this +/// will block until the server is running. It is safe to call this multiple times, +/// because the address is shared among all threads in a process. +pub(crate) fn log_server() -> Connection { + static LOG_SERVER_CONNECTION: AtomicU32 = AtomicU32::new(0); + + let cid = LOG_SERVER_CONNECTION.load(Ordering::Relaxed); + if cid != 0 { + return cid.into(); + } + + let cid = crate::os::xous::ffi::connect("xous-log-server ".try_into().unwrap()).unwrap(); + LOG_SERVER_CONNECTION.store(cid.into(), Ordering::Relaxed); + cid +} diff --git a/library/std/src/os/xous/services/systime.rs b/library/std/src/os/xous/services/systime.rs new file mode 100644 index 00000000000..bbb875c6942 --- /dev/null +++ b/library/std/src/os/xous/services/systime.rs @@ -0,0 +1,28 @@ +use crate::os::xous::ffi::{connect, Connection}; +use core::sync::atomic::{AtomicU32, Ordering}; + +pub(crate) enum SystimeScalar { + GetUtcTimeMs, +} + +impl Into<[usize; 5]> for SystimeScalar { + fn into(self) -> [usize; 5] { + match self { + SystimeScalar::GetUtcTimeMs => [3, 0, 0, 0, 0], + } + } +} + +/// Return a `Connection` to the systime server. This server is used for reporting the +/// realtime clock. +pub(crate) fn systime_server() -> Connection { + static SYSTIME_SERVER_CONNECTION: AtomicU32 = AtomicU32::new(0); + let cid = SYSTIME_SERVER_CONNECTION.load(Ordering::Relaxed); + if cid != 0 { + return cid.into(); + } + + let cid = connect("timeserverpublic".try_into().unwrap()).unwrap(); + SYSTIME_SERVER_CONNECTION.store(cid.into(), Ordering::Relaxed); + cid +} diff --git a/library/std/src/os/xous/services/ticktimer.rs b/library/std/src/os/xous/services/ticktimer.rs new file mode 100644 index 00000000000..7759303fdbe --- /dev/null +++ b/library/std/src/os/xous/services/ticktimer.rs @@ -0,0 +1,42 @@ +use crate::os::xous::ffi::Connection; +use core::sync::atomic::{AtomicU32, Ordering}; + +pub(crate) enum TicktimerScalar { + ElapsedMs, + SleepMs(usize), + LockMutex(usize /* cookie */), + UnlockMutex(usize /* cookie */), + WaitForCondition(usize /* cookie */, usize /* timeout (ms) */), + NotifyCondition(usize /* cookie */, usize /* count */), + FreeMutex(usize /* cookie */), + FreeCondition(usize /* cookie */), +} + +impl Into<[usize; 5]> for TicktimerScalar { + fn into(self) -> [usize; 5] { + match self { + TicktimerScalar::ElapsedMs => [0, 0, 0, 0, 0], + TicktimerScalar::SleepMs(msecs) => [1, msecs, 0, 0, 0], + TicktimerScalar::LockMutex(cookie) => [6, cookie, 0, 0, 0], + TicktimerScalar::UnlockMutex(cookie) => [7, cookie, 0, 0, 0], + TicktimerScalar::WaitForCondition(cookie, timeout_ms) => [8, cookie, timeout_ms, 0, 0], + TicktimerScalar::NotifyCondition(cookie, count) => [9, cookie, count, 0, 0], + TicktimerScalar::FreeMutex(cookie) => [10, cookie, 0, 0, 0], + TicktimerScalar::FreeCondition(cookie) => [11, cookie, 0, 0, 0], + } + } +} + +/// Return a `Connection` to the ticktimer server. This server is used for synchronization +/// primitives such as sleep, Mutex, and Condvar. +pub(crate) fn ticktimer_server() -> Connection { + static TICKTIMER_SERVER_CONNECTION: AtomicU32 = AtomicU32::new(0); + let cid = TICKTIMER_SERVER_CONNECTION.load(Ordering::Relaxed); + if cid != 0 { + return cid.into(); + } + + let cid = crate::os::xous::ffi::connect("ticktimer-server".try_into().unwrap()).unwrap(); + TICKTIMER_SERVER_CONNECTION.store(cid.into(), Ordering::Relaxed); + cid +} diff --git a/library/std/src/process.rs b/library/std/src/process.rs index 762a1e9b408..5df1105e264 100644 --- a/library/std/src/process.rs +++ b/library/std/src/process.rs @@ -101,7 +101,7 @@ #![stable(feature = "process", since = "1.0.0")] #![deny(unsafe_op_in_unsafe_fn)] -#[cfg(all(test, not(any(target_os = "emscripten", target_env = "sgx"))))] +#[cfg(all(test, not(any(target_os = "emscripten", target_env = "sgx", target_os = "xous"))))] mod tests; use crate::io::prelude::*; diff --git a/library/std/src/sys/mod.rs b/library/std/src/sys/mod.rs index 63bd783746b..457eb782ccc 100644 --- a/library/std/src/sys/mod.rs +++ b/library/std/src/sys/mod.rs @@ -44,6 +44,9 @@ cfg_if::cfg_if! { } else if #[cfg(target_family = "wasm")] { mod wasm; pub use self::wasm::*; + } else if #[cfg(target_os = "xous")] { + mod xous; + pub use self::xous::*; } else if #[cfg(all(target_vendor = "fortanix", target_env = "sgx"))] { mod sgx; pub use self::sgx::*; diff --git a/library/std/src/sys/xous/alloc.rs b/library/std/src/sys/xous/alloc.rs new file mode 100644 index 00000000000..b3a3e691e0d --- /dev/null +++ b/library/std/src/sys/xous/alloc.rs @@ -0,0 +1,62 @@ +use crate::alloc::{GlobalAlloc, Layout, System}; + +static mut DLMALLOC: dlmalloc::Dlmalloc = dlmalloc::Dlmalloc::new(); + +#[stable(feature = "alloc_system_type", since = "1.28.0")] +unsafe impl GlobalAlloc for System { + #[inline] + unsafe fn alloc(&self, layout: Layout) -> *mut u8 { + // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access. + // Calling malloc() is safe because preconditions on this function match the trait method preconditions. + let _lock = lock::lock(); + unsafe { DLMALLOC.malloc(layout.size(), layout.align()) } + } + + #[inline] + unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 { + // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access. + // Calling calloc() is safe because preconditions on this function match the trait method preconditions. + let _lock = lock::lock(); + unsafe { DLMALLOC.calloc(layout.size(), layout.align()) } + } + + #[inline] + unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) { + // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access. + // Calling free() is safe because preconditions on this function match the trait method preconditions. + let _lock = lock::lock(); + unsafe { DLMALLOC.free(ptr, layout.size(), layout.align()) } + } + + #[inline] + unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 { + // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access. + // Calling realloc() is safe because preconditions on this function match the trait method preconditions. + let _lock = lock::lock(); + unsafe { DLMALLOC.realloc(ptr, layout.size(), layout.align(), new_size) } + } +} + +mod lock { + use crate::sync::atomic::{AtomicI32, Ordering::SeqCst}; + + static LOCKED: AtomicI32 = AtomicI32::new(0); + + pub struct DropLock; + + pub fn lock() -> DropLock { + loop { + if LOCKED.swap(1, SeqCst) == 0 { + return DropLock; + } + crate::os::xous::ffi::do_yield(); + } + } + + impl Drop for DropLock { + fn drop(&mut self) { + let r = LOCKED.swap(0, SeqCst); + debug_assert_eq!(r, 1); + } + } +} diff --git a/library/std/src/sys/xous/locks/condvar.rs b/library/std/src/sys/xous/locks/condvar.rs new file mode 100644 index 00000000000..1bb38dfa341 --- /dev/null +++ b/library/std/src/sys/xous/locks/condvar.rs @@ -0,0 +1,111 @@ +use super::mutex::Mutex; +use crate::os::xous::ffi::{blocking_scalar, scalar}; +use crate::os::xous::services::ticktimer_server; +use crate::sync::Mutex as StdMutex; +use crate::time::Duration; + +// The implementation is inspired by Andrew D. Birrell's paper +// "Implementing Condition Variables with Semaphores" + +pub struct Condvar { + counter: StdMutex<usize>, +} + +unsafe impl Send for Condvar {} +unsafe impl Sync for Condvar {} + +impl Condvar { + #[inline] + #[rustc_const_stable(feature = "const_locks", since = "1.63.0")] + pub const fn new() -> Condvar { + Condvar { counter: StdMutex::new(0) } + } + + pub fn notify_one(&self) { + let mut counter = self.counter.lock().unwrap(); + if *counter <= 0 { + return; + } else { + *counter -= 1; + } + let result = blocking_scalar( + ticktimer_server(), + crate::os::xous::services::TicktimerScalar::NotifyCondition(self.index(), 1).into(), + ); + drop(counter); + result.expect("failure to send NotifyCondition command"); + } + + pub fn notify_all(&self) { + let mut counter = self.counter.lock().unwrap(); + if *counter <= 0 { + return; + } + let result = blocking_scalar( + ticktimer_server(), + crate::os::xous::services::TicktimerScalar::NotifyCondition(self.index(), *counter) + .into(), + ); + *counter = 0; + drop(counter); + + result.expect("failure to send NotifyCondition command"); + } + + fn index(&self) -> usize { + self as *const Condvar as usize + } + + pub unsafe fn wait(&self, mutex: &Mutex) { + let mut counter = self.counter.lock().unwrap(); + *counter += 1; + unsafe { mutex.unlock() }; + drop(counter); + + let result = blocking_scalar( + ticktimer_server(), + crate::os::xous::services::TicktimerScalar::WaitForCondition(self.index(), 0).into(), + ); + unsafe { mutex.lock() }; + + result.expect("Ticktimer: failure to send WaitForCondition command"); + } + + pub unsafe fn wait_timeout(&self, mutex: &Mutex, dur: Duration) -> bool { + let mut counter = self.counter.lock().unwrap(); + *counter += 1; + unsafe { mutex.unlock() }; + drop(counter); + + let mut millis = dur.as_millis() as usize; + if millis == 0 { + millis = 1; + } + + let result = blocking_scalar( + ticktimer_server(), + crate::os::xous::services::TicktimerScalar::WaitForCondition(self.index(), millis) + .into(), + ); + unsafe { mutex.lock() }; + + let result = result.expect("Ticktimer: failure to send WaitForCondition command")[0] == 0; + + // If we awoke due to a timeout, decrement the wake count, as that would not have + // been done in the `notify()` call. + if !result { + *self.counter.lock().unwrap() -= 1; + } + result + } +} + +impl Drop for Condvar { + fn drop(&mut self) { + scalar( + ticktimer_server(), + crate::os::xous::services::TicktimerScalar::FreeCondition(self.index()).into(), + ) + .ok(); + } +} diff --git a/library/std/src/sys/xous/locks/mod.rs b/library/std/src/sys/xous/locks/mod.rs new file mode 100644 index 00000000000..f3c5c5d9fb0 --- /dev/null +++ b/library/std/src/sys/xous/locks/mod.rs @@ -0,0 +1,7 @@ +mod condvar; +mod mutex; +mod rwlock; + +pub use condvar::*; +pub use mutex::*; +pub use rwlock::*; diff --git a/library/std/src/sys/xous/locks/mutex.rs b/library/std/src/sys/xous/locks/mutex.rs new file mode 100644 index 00000000000..ea51776d54e --- /dev/null +++ b/library/std/src/sys/xous/locks/mutex.rs @@ -0,0 +1,116 @@ +use crate::os::xous::ffi::{blocking_scalar, do_yield, scalar}; +use crate::os::xous::services::ticktimer_server; +use crate::sync::atomic::{AtomicBool, AtomicUsize, Ordering::Relaxed, Ordering::SeqCst}; + +pub struct Mutex { + /// The "locked" value indicates how many threads are waiting on this + /// Mutex. Possible values are: + /// 0: The lock is unlocked + /// 1: The lock is locked and uncontended + /// >=2: The lock is locked and contended + /// + /// A lock is "contended" when there is more than one thread waiting + /// for a lock, or it is locked for long periods of time. Rather than + /// spinning, these locks send a Message to the ticktimer server + /// requesting that they be woken up when a lock is unlocked. + locked: AtomicUsize, + + /// Whether this Mutex ever was contended, and therefore made a trip + /// to the ticktimer server. If this was never set, then we were never + /// on the slow path and can skip deregistering the mutex. + contended: AtomicBool, +} + +impl Mutex { + #[inline] + #[rustc_const_stable(feature = "const_locks", since = "1.63.0")] + pub const fn new() -> Mutex { + Mutex { locked: AtomicUsize::new(0), contended: AtomicBool::new(false) } + } + + fn index(&self) -> usize { + self as *const Mutex as usize + } + + #[inline] + pub unsafe fn lock(&self) { + // Try multiple times to acquire the lock without resorting to the ticktimer + // server. For locks that are held for a short amount of time, this will + // result in the ticktimer server never getting invoked. The `locked` value + // will be either 0 or 1. + for _attempts in 0..3 { + if unsafe { self.try_lock() } { + return; + } + do_yield(); + } + + // Try one more time to lock. If the lock is released between the previous code and + // here, then the inner `locked` value will be 1 at the end of this. If it was not + // locked, then the value will be more than 1, for example if there are multiple other + // threads waiting on this lock. + if unsafe { self.try_lock_or_poison() } { + return; + } + + // When this mutex is dropped, we will need to deregister it with the server. + self.contended.store(true, Relaxed); + + // The lock is now "contended". When the lock is released, a Message will get sent to the + // ticktimer server to wake it up. Note that this may already have happened, so the actual + // value of `lock` may be anything (0, 1, 2, ...). + blocking_scalar( + ticktimer_server(), + crate::os::xous::services::TicktimerScalar::LockMutex(self.index()).into(), + ) + .expect("failure to send LockMutex command"); + } + + #[inline] + pub unsafe fn unlock(&self) { + let prev = self.locked.fetch_sub(1, SeqCst); + + // If the previous value was 1, then this was a "fast path" unlock, so no + // need to involve the Ticktimer server + if prev == 1 { + return; + } + + // If it was 0, then something has gone seriously wrong and the counter + // has just wrapped around. + if prev == 0 { + panic!("mutex lock count underflowed"); + } + + // Unblock one thread that is waiting on this message. + scalar( + ticktimer_server(), + crate::os::xous::services::TicktimerScalar::UnlockMutex(self.index()).into(), + ) + .expect("failure to send UnlockMutex command"); + } + + #[inline] + pub unsafe fn try_lock(&self) -> bool { + self.locked.compare_exchange(0, 1, SeqCst, SeqCst).is_ok() + } + + #[inline] + pub unsafe fn try_lock_or_poison(&self) -> bool { + self.locked.fetch_add(1, SeqCst) == 0 + } +} + +impl Drop for Mutex { + fn drop(&mut self) { + // If there was Mutex contention, then we involved the ticktimer. Free + // the resources associated with this Mutex as it is deallocated. + if self.contended.load(Relaxed) { + scalar( + ticktimer_server(), + crate::os::xous::services::TicktimerScalar::FreeMutex(self.index()).into(), + ) + .ok(); + } + } +} diff --git a/library/std/src/sys/xous/locks/rwlock.rs b/library/std/src/sys/xous/locks/rwlock.rs new file mode 100644 index 00000000000..618da758adf --- /dev/null +++ b/library/std/src/sys/xous/locks/rwlock.rs @@ -0,0 +1,72 @@ +use crate::os::xous::ffi::do_yield; +use crate::sync::atomic::{AtomicIsize, Ordering::SeqCst}; + +pub struct RwLock { + /// The "mode" value indicates how many threads are waiting on this + /// Mutex. Possible values are: + /// -1: The lock is locked for writing + /// 0: The lock is unlocked + /// >=1: The lock is locked for reading + /// + /// This currently spins waiting for the lock to be freed. An + /// optimization would be to involve the ticktimer server to + /// coordinate unlocks. + mode: AtomicIsize, +} + +unsafe impl Send for RwLock {} +unsafe impl Sync for RwLock {} + +impl RwLock { + #[inline] + #[rustc_const_stable(feature = "const_locks", since = "1.63.0")] + pub const fn new() -> RwLock { + RwLock { mode: AtomicIsize::new(0) } + } + + #[inline] + pub unsafe fn read(&self) { + while !unsafe { self.try_read() } { + do_yield(); + } + } + + #[inline] + pub unsafe fn try_read(&self) -> bool { + // Non-atomically determine the current value. + let current = self.mode.load(SeqCst); + + // If it's currently locked for writing, then we cannot read. + if current < 0 { + return false; + } + + // Attempt to lock. If the `current` value has changed, then this + // operation will fail and we will not obtain the lock even if we + // could potentially keep it. + let new = current + 1; + self.mode.compare_exchange(current, new, SeqCst, SeqCst).is_ok() + } + + #[inline] + pub unsafe fn write(&self) { + while !unsafe { self.try_write() } { + do_yield(); + } + } + + #[inline] + pub unsafe fn try_write(&self) -> bool { + self.mode.compare_exchange(0, -1, SeqCst, SeqCst).is_ok() + } + + #[inline] + pub unsafe fn read_unlock(&self) { + self.mode.fetch_sub(1, SeqCst); + } + + #[inline] + pub unsafe fn write_unlock(&self) { + assert_eq!(self.mode.compare_exchange(-1, 0, SeqCst, SeqCst), Ok(-1)); + } +} diff --git a/library/std/src/sys/xous/mod.rs b/library/std/src/sys/xous/mod.rs new file mode 100644 index 00000000000..6d5c218d195 --- /dev/null +++ b/library/std/src/sys/xous/mod.rs @@ -0,0 +1,37 @@ +#![deny(unsafe_op_in_unsafe_fn)] + +pub mod alloc; +#[path = "../unsupported/args.rs"] +pub mod args; +#[path = "../unix/cmath.rs"] +pub mod cmath; +#[path = "../unsupported/env.rs"] +pub mod env; +#[path = "../unsupported/fs.rs"] +pub mod fs; +#[path = "../unsupported/io.rs"] +pub mod io; +pub mod locks; +#[path = "../unsupported/net.rs"] +pub mod net; +#[path = "../unsupported/once.rs"] +pub mod once; +pub mod os; +#[path = "../unix/os_str.rs"] +pub mod os_str; +#[path = "../unix/path.rs"] +pub mod path; +#[path = "../unsupported/pipe.rs"] +pub mod pipe; +#[path = "../unsupported/process.rs"] +pub mod process; +pub mod stdio; +pub mod thread; +pub mod thread_local_key; +#[path = "../unsupported/thread_parking.rs"] +pub mod thread_parking; +pub mod time; + +#[path = "../unsupported/common.rs"] +mod common; +pub use common::*; diff --git a/library/std/src/sys/xous/os.rs b/library/std/src/sys/xous/os.rs new file mode 100644 index 00000000000..3d19fa4b31a --- /dev/null +++ b/library/std/src/sys/xous/os.rs @@ -0,0 +1,147 @@ +use super::unsupported; +use crate::error::Error as StdError; +use crate::ffi::{OsStr, OsString}; +use crate::fmt; +use crate::io; +use crate::marker::PhantomData; +use crate::os::xous::ffi::Error as XousError; +use crate::path::{self, PathBuf}; + +#[cfg(not(test))] +mod c_compat { + use crate::os::xous::ffi::exit; + extern "C" { + fn main() -> u32; + } + + #[no_mangle] + pub extern "C" fn abort() { + exit(1); + } + + #[no_mangle] + pub extern "C" fn _start() { + exit(unsafe { main() }); + } + + // This function is needed by the panic runtime. The symbol is named in + // pre-link args for the target specification, so keep that in sync. + #[no_mangle] + // NB. used by both libunwind and libpanic_abort + pub extern "C" fn __rust_abort() -> ! { + exit(101); + } +} + +pub fn errno() -> i32 { + 0 +} + +pub fn error_string(errno: i32) -> String { + Into::<XousError>::into(errno).to_string() +} + +pub fn getcwd() -> io::Result<PathBuf> { + unsupported() +} + +pub fn chdir(_: &path::Path) -> io::Result<()> { + unsupported() +} + +pub struct SplitPaths<'a>(!, PhantomData<&'a ()>); + +pub fn split_paths(_unparsed: &OsStr) -> SplitPaths<'_> { + panic!("unsupported") +} + +impl<'a> Iterator for SplitPaths<'a> { + type Item = PathBuf; + fn next(&mut self) -> Option<PathBuf> { + self.0 + } +} + +#[derive(Debug)] +pub struct JoinPathsError; + +pub fn join_paths<I, T>(_paths: I) -> Result<OsString, JoinPathsError> +where + I: Iterator<Item = T>, + T: AsRef<OsStr>, +{ + Err(JoinPathsError) +} + +impl fmt::Display for JoinPathsError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + "not supported on this platform yet".fmt(f) + } +} + +impl StdError for JoinPathsError { + #[allow(deprecated)] + fn description(&self) -> &str { + "not supported on this platform yet" + } +} + +pub fn current_exe() -> io::Result<PathBuf> { + unsupported() +} + +pub struct Env(!); + +impl Env { + // FIXME(https://github.com/rust-lang/rust/issues/114583): Remove this when <OsStr as Debug>::fmt matches <str as Debug>::fmt. + pub fn str_debug(&self) -> impl fmt::Debug + '_ { + let Self(inner) = self; + match *inner {} + } +} + +impl fmt::Debug for Env { + fn fmt(&self, _: &mut fmt::Formatter<'_>) -> fmt::Result { + let Self(inner) = self; + match *inner {} + } +} + +impl Iterator for Env { + type Item = (OsString, OsString); + fn next(&mut self) -> Option<(OsString, OsString)> { + self.0 + } +} + +pub fn env() -> Env { + panic!("not supported on this platform") +} + +pub fn getenv(_: &OsStr) -> Option<OsString> { + None +} + +pub fn setenv(_: &OsStr, _: &OsStr) -> io::Result<()> { + Err(io::const_io_error!(io::ErrorKind::Unsupported, "cannot set env vars on this platform")) +} + +pub fn unsetenv(_: &OsStr) -> io::Result<()> { + Err(io::const_io_error!(io::ErrorKind::Unsupported, "cannot unset env vars on this platform")) +} + +pub fn temp_dir() -> PathBuf { + panic!("no filesystem on this platform") +} + +pub fn home_dir() -> Option<PathBuf> { + None +} + +pub fn exit(code: i32) -> ! { + crate::os::xous::ffi::exit(code as u32); +} + +pub fn getpid() -> u32 { + panic!("no pids on this platform") +} diff --git a/library/std/src/sys/xous/stdio.rs b/library/std/src/sys/xous/stdio.rs new file mode 100644 index 00000000000..2ac694641ba --- /dev/null +++ b/library/std/src/sys/xous/stdio.rs @@ -0,0 +1,131 @@ +use crate::io; + +pub struct Stdin; +pub struct Stdout {} +pub struct Stderr; + +use crate::os::xous::ffi::{lend, try_lend, try_scalar, Connection}; +use crate::os::xous::services::{log_server, try_connect, LogScalar}; + +impl Stdin { + pub const fn new() -> Stdin { + Stdin + } +} + +impl io::Read for Stdin { + fn read(&mut self, _buf: &mut [u8]) -> io::Result<usize> { + Ok(0) + } +} + +impl Stdout { + pub const fn new() -> Stdout { + Stdout {} + } +} + +impl io::Write for Stdout { + fn write(&mut self, buf: &[u8]) -> io::Result<usize> { + #[repr(align(4096))] + struct LendBuffer([u8; 4096]); + let mut lend_buffer = LendBuffer([0u8; 4096]); + let connection = log_server(); + for chunk in buf.chunks(lend_buffer.0.len()) { + for (dest, src) in lend_buffer.0.iter_mut().zip(chunk) { + *dest = *src; + } + lend(connection, 1, &lend_buffer.0, 0, chunk.len()).unwrap(); + } + Ok(buf.len()) + } + + fn flush(&mut self) -> io::Result<()> { + Ok(()) + } +} + +impl Stderr { + pub const fn new() -> Stderr { + Stderr + } +} + +impl io::Write for Stderr { + fn write(&mut self, buf: &[u8]) -> io::Result<usize> { + #[repr(align(4096))] + struct LendBuffer([u8; 4096]); + let mut lend_buffer = LendBuffer([0u8; 4096]); + let connection = log_server(); + for chunk in buf.chunks(lend_buffer.0.len()) { + for (dest, src) in lend_buffer.0.iter_mut().zip(chunk) { + *dest = *src; + } + lend(connection, 1, &lend_buffer.0, 0, chunk.len()).unwrap(); + } + Ok(buf.len()) + } + + fn flush(&mut self) -> io::Result<()> { + Ok(()) + } +} + +pub const STDIN_BUF_SIZE: usize = 0; + +pub fn is_ebadf(_err: &io::Error) -> bool { + true +} + +#[derive(Copy, Clone)] +pub struct PanicWriter { + log: Connection, + gfx: Option<Connection>, +} + +impl io::Write for PanicWriter { + fn write(&mut self, s: &[u8]) -> core::result::Result<usize, io::Error> { + for c in s.chunks(core::mem::size_of::<usize>() * 4) { + // Text is grouped into 4x `usize` words. The id is 1100 plus + // the number of characters in this message. + // Ignore errors since we're already panicking. + try_scalar(self.log, LogScalar::AppendPanicMessage(&c).into()).ok(); + } + + // Serialize the text to the graphics panic handler, only if we were able + // to acquire a connection to it. Text length is encoded in the `valid` field, + // the data itself in the buffer. Typically several messages are require to + // fully transmit the entire panic message. + if let Some(gfx) = self.gfx { + #[repr(C, align(4096))] + struct Request([u8; 4096]); + let mut request = Request([0u8; 4096]); + for (&s, d) in s.iter().zip(request.0.iter_mut()) { + *d = s; + } + try_lend(gfx, 0 /* AppendPanicText */, &request.0, 0, s.len()).ok(); + } + Ok(s.len()) + } + + // Tests show that this does not seem to be reliably called at the end of a panic + // print, so, we can't rely on this to e.g. trigger a graphics update. + fn flush(&mut self) -> io::Result<()> { + Ok(()) + } +} + +pub fn panic_output() -> Option<impl io::Write> { + // Generally this won't fail because every server has already connected, so + // this is likely to succeed. + let log = log_server(); + + // Send the "We're panicking" message (1000). + try_scalar(log, LogScalar::BeginPanic.into()).ok(); + + // This is will fail in the case that the connection table is full, or if the + // graphics server is not running. Most servers do not already have this connection. + let gfx = try_connect("panic-to-screen!"); + + Some(PanicWriter { log, gfx }) +} diff --git a/library/std/src/sys/xous/thread.rs b/library/std/src/sys/xous/thread.rs new file mode 100644 index 00000000000..78c68de7bf3 --- /dev/null +++ b/library/std/src/sys/xous/thread.rs @@ -0,0 +1,144 @@ +use crate::ffi::CStr; +use crate::io; +use crate::num::NonZeroUsize; +use crate::os::xous::ffi::{ + blocking_scalar, create_thread, do_yield, join_thread, map_memory, update_memory_flags, + MemoryFlags, Syscall, ThreadId, +}; +use crate::os::xous::services::{ticktimer_server, TicktimerScalar}; +use crate::time::Duration; +use core::arch::asm; + +pub struct Thread { + tid: ThreadId, +} + +pub const DEFAULT_MIN_STACK_SIZE: usize = 131072; +const MIN_STACK_SIZE: usize = 4096; +pub const GUARD_PAGE_SIZE: usize = 4096; + +impl Thread { + // unsafe: see thread::Builder::spawn_unchecked for safety requirements + pub unsafe fn new(stack: usize, p: Box<dyn FnOnce()>) -> io::Result<Thread> { + let p = Box::into_raw(Box::new(p)); + let mut stack_size = crate::cmp::max(stack, MIN_STACK_SIZE); + + if (stack_size & 4095) != 0 { + stack_size = (stack_size + 4095) & !4095; + } + + // Allocate the whole thing, then divide it up after the fact. This ensures that + // even if there's a context switch during this function, the whole stack plus + // guard pages will remain contiguous. + let stack_plus_guard_pages: &mut [u8] = unsafe { + map_memory( + None, + None, + GUARD_PAGE_SIZE + stack_size + GUARD_PAGE_SIZE, + MemoryFlags::R | MemoryFlags::W | MemoryFlags::X, + ) + } + .map_err(|code| io::Error::from_raw_os_error(code as i32))?; + + // No access to this page. Note: Write-only pages are illegal, and will + // cause an access violation. + unsafe { + update_memory_flags(&mut stack_plus_guard_pages[0..GUARD_PAGE_SIZE], MemoryFlags::W) + .map_err(|code| io::Error::from_raw_os_error(code as i32))? + }; + + // No access to this page. Note: Write-only pages are illegal, and will + // cause an access violation. + unsafe { + update_memory_flags( + &mut stack_plus_guard_pages[(GUARD_PAGE_SIZE + stack_size)..], + MemoryFlags::W, + ) + .map_err(|code| io::Error::from_raw_os_error(code as i32))? + }; + + let guard_page_pre = stack_plus_guard_pages.as_ptr() as usize; + let tid = create_thread( + thread_start as *mut usize, + &mut stack_plus_guard_pages[GUARD_PAGE_SIZE..(stack_size + GUARD_PAGE_SIZE)], + p as usize, + guard_page_pre, + stack_size, + 0, + ) + .map_err(|code| io::Error::from_raw_os_error(code as i32))?; + + extern "C" fn thread_start(main: *mut usize, guard_page_pre: usize, stack_size: usize) { + unsafe { + // Finally, let's run some code. + Box::from_raw(main as *mut Box<dyn FnOnce()>)(); + } + + // Destroy TLS, which will free the TLS page and call the destructor for + // any thread local storage. + unsafe { + crate::sys::thread_local_key::destroy_tls(); + } + + // Deallocate the stack memory, along with the guard pages. Afterwards, + // exit the thread by returning to the magic address 0xff80_3000usize, + // which tells the kernel to deallocate this thread. + let mapped_memory_base = guard_page_pre; + let mapped_memory_length = GUARD_PAGE_SIZE + stack_size + GUARD_PAGE_SIZE; + unsafe { + asm!( + "ecall", + "ret", + in("a0") Syscall::UnmapMemory as usize, + in("a1") mapped_memory_base, + in("a2") mapped_memory_length, + in("ra") 0xff80_3000usize, + options(nomem, nostack, noreturn) + ); + } + } + + Ok(Thread { tid }) + } + + pub fn yield_now() { + do_yield(); + } + + pub fn set_name(_name: &CStr) { + // nope + } + + pub fn sleep(dur: Duration) { + // Because the sleep server works on units of `usized milliseconds`, split + // the messages up into these chunks. This means we may run into issues + // if you try to sleep a thread for more than 49 days on a 32-bit system. + let mut millis = dur.as_millis(); + while millis > 0 { + let sleep_duration = + if millis > (usize::MAX as _) { usize::MAX } else { millis as usize }; + blocking_scalar(ticktimer_server(), TicktimerScalar::SleepMs(sleep_duration).into()) + .expect("failed to send message to ticktimer server"); + millis -= sleep_duration as u128; + } + } + + pub fn join(self) { + join_thread(self.tid).unwrap(); + } +} + +pub fn available_parallelism() -> io::Result<NonZeroUsize> { + // We're unicore right now. + Ok(unsafe { NonZeroUsize::new_unchecked(1) }) +} + +pub mod guard { + pub type Guard = !; + pub unsafe fn current() -> Option<Guard> { + None + } + pub unsafe fn init() -> Option<Guard> { + None + } +} diff --git a/library/std/src/sys/xous/thread_local_key.rs b/library/std/src/sys/xous/thread_local_key.rs new file mode 100644 index 00000000000..3771ea65700 --- /dev/null +++ b/library/std/src/sys/xous/thread_local_key.rs @@ -0,0 +1,190 @@ +use crate::mem::ManuallyDrop; +use crate::ptr; +use crate::sync::atomic::AtomicPtr; +use crate::sync::atomic::AtomicUsize; +use crate::sync::atomic::Ordering::SeqCst; +use core::arch::asm; + +use crate::os::xous::ffi::{map_memory, unmap_memory, MemoryFlags}; + +/// Thread Local Storage +/// +/// Currently, we are limited to 1023 TLS entries. The entries +/// live in a page of memory that's unique per-process, and is +/// stored in the `$tp` register. If this register is 0, then +/// TLS has not been initialized and thread cleanup can be skipped. +/// +/// The index into this register is the `key`. This key is identical +/// between all threads, but indexes a different offset within this +/// pointer. +pub type Key = usize; + +pub type Dtor = unsafe extern "C" fn(*mut u8); + +const TLS_MEMORY_SIZE: usize = 4096; + +/// TLS keys start at `1` to mimic POSIX. +static TLS_KEY_INDEX: AtomicUsize = AtomicUsize::new(1); + +fn tls_ptr_addr() -> *mut usize { + let mut tp: usize; + unsafe { + asm!( + "mv {}, tp", + out(reg) tp, + ); + } + core::ptr::from_exposed_addr_mut::<usize>(tp) +} + +/// Create an area of memory that's unique per thread. This area will +/// contain all thread local pointers. +fn tls_ptr() -> *mut usize { + let mut tp = tls_ptr_addr(); + + // If the TP register is `0`, then this thread hasn't initialized + // its TLS yet. Allocate a new page to store this memory. + if tp.is_null() { + tp = unsafe { + map_memory( + None, + None, + TLS_MEMORY_SIZE / core::mem::size_of::<usize>(), + MemoryFlags::R | MemoryFlags::W, + ) + } + .expect("Unable to allocate memory for thread local storage") + .as_mut_ptr(); + + unsafe { + // Key #0 is currently unused. + (tp).write_volatile(0); + + // Set the thread's `$tp` register + asm!( + "mv tp, {}", + in(reg) tp as usize, + ); + } + } + tp +} + +/// Allocate a new TLS key. These keys are shared among all threads. +fn tls_alloc() -> usize { + TLS_KEY_INDEX.fetch_add(1, SeqCst) +} + +#[inline] +pub unsafe fn create(dtor: Option<Dtor>) -> Key { + let key = tls_alloc(); + if let Some(f) = dtor { + unsafe { register_dtor(key, f) }; + } + key +} + +#[inline] +pub unsafe fn set(key: Key, value: *mut u8) { + assert!((key < 1022) && (key >= 1)); + unsafe { tls_ptr().add(key).write_volatile(value as usize) }; +} + +#[inline] +pub unsafe fn get(key: Key) -> *mut u8 { + assert!((key < 1022) && (key >= 1)); + core::ptr::from_exposed_addr_mut::<u8>(unsafe { tls_ptr().add(key).read_volatile() }) +} + +#[inline] +pub unsafe fn destroy(_key: Key) { + panic!("can't destroy keys on Xous"); +} + +// ------------------------------------------------------------------------- +// Dtor registration (stolen from Windows) +// +// Xous has no native support for running destructors so we manage our own +// list of destructors to keep track of how to destroy keys. We then install a +// callback later to get invoked whenever a thread exits, running all +// appropriate destructors. +// +// Currently unregistration from this list is not supported. A destructor can be +// registered but cannot be unregistered. There's various simplifying reasons +// for doing this, the big ones being: +// +// 1. Currently we don't even support deallocating TLS keys, so normal operation +// doesn't need to deallocate a destructor. +// 2. There is no point in time where we know we can unregister a destructor +// because it could always be getting run by some remote thread. +// +// Typically processes have a statically known set of TLS keys which is pretty +// small, and we'd want to keep this memory alive for the whole process anyway +// really. +// +// Perhaps one day we can fold the `Box` here into a static allocation, +// expanding the `StaticKey` structure to contain not only a slot for the TLS +// key but also a slot for the destructor queue on windows. An optimization for +// another day! + +static DTORS: AtomicPtr<Node> = AtomicPtr::new(ptr::null_mut()); + +struct Node { + dtor: Dtor, + key: Key, + next: *mut Node, +} + +unsafe fn register_dtor(key: Key, dtor: Dtor) { + let mut node = ManuallyDrop::new(Box::new(Node { key, dtor, next: ptr::null_mut() })); + + let mut head = DTORS.load(SeqCst); + loop { + node.next = head; + match DTORS.compare_exchange(head, &mut **node, SeqCst, SeqCst) { + Ok(_) => return, // nothing to drop, we successfully added the node to the list + Err(cur) => head = cur, + } + } +} + +pub unsafe fn destroy_tls() { + let tp = tls_ptr_addr(); + + // If the pointer address is 0, then this thread has no TLS. + if tp.is_null() { + return; + } + unsafe { run_dtors() }; + + // Finally, free the TLS array + unsafe { + unmap_memory(core::slice::from_raw_parts_mut( + tp, + TLS_MEMORY_SIZE / core::mem::size_of::<usize>(), + )) + .unwrap() + }; +} + +unsafe fn run_dtors() { + let mut any_run = true; + for _ in 0..5 { + if !any_run { + break; + } + any_run = false; + let mut cur = DTORS.load(SeqCst); + while !cur.is_null() { + let ptr = unsafe { get((*cur).key) }; + + if !ptr.is_null() { + unsafe { set((*cur).key, ptr::null_mut()) }; + unsafe { ((*cur).dtor)(ptr as *mut _) }; + any_run = true; + } + + unsafe { cur = (*cur).next }; + } + } +} diff --git a/library/std/src/sys/xous/time.rs b/library/std/src/sys/xous/time.rs new file mode 100644 index 00000000000..4e4ae67efff --- /dev/null +++ b/library/std/src/sys/xous/time.rs @@ -0,0 +1,57 @@ +use crate::os::xous::ffi::blocking_scalar; +use crate::os::xous::services::{ + systime_server, ticktimer_server, SystimeScalar::GetUtcTimeMs, TicktimerScalar::ElapsedMs, +}; +use crate::time::Duration; + +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)] +pub struct Instant(Duration); + +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)] +pub struct SystemTime(Duration); + +pub const UNIX_EPOCH: SystemTime = SystemTime(Duration::from_secs(0)); + +impl Instant { + pub fn now() -> Instant { + let result = blocking_scalar(ticktimer_server(), ElapsedMs.into()) + .expect("failed to request elapsed_ms"); + let lower = result[0]; + let upper = result[1]; + Instant { 0: Duration::from_millis(lower as u64 | (upper as u64) << 32) } + } + + pub fn checked_sub_instant(&self, other: &Instant) -> Option<Duration> { + self.0.checked_sub(other.0) + } + + pub fn checked_add_duration(&self, other: &Duration) -> Option<Instant> { + self.0.checked_add(*other).map(Instant) + } + + pub fn checked_sub_duration(&self, other: &Duration) -> Option<Instant> { + self.0.checked_sub(*other).map(Instant) + } +} + +impl SystemTime { + pub fn now() -> SystemTime { + let result = blocking_scalar(systime_server(), GetUtcTimeMs.into()) + .expect("failed to request utc time in ms"); + let lower = result[0]; + let upper = result[1]; + SystemTime { 0: Duration::from_millis((upper as u64) << 32 | lower as u64) } + } + + pub fn sub_time(&self, other: &SystemTime) -> Result<Duration, Duration> { + self.0.checked_sub(other.0).ok_or_else(|| other.0 - self.0) + } + + pub fn checked_add_duration(&self, other: &Duration) -> Option<SystemTime> { + Some(SystemTime(self.0.checked_add(*other)?)) + } + + pub fn checked_sub_duration(&self, other: &Duration) -> Option<SystemTime> { + Some(SystemTime(self.0.checked_sub(*other)?)) + } +} diff --git a/library/std/src/sys_common/mod.rs b/library/std/src/sys_common/mod.rs index e9c727cbbd1..f7d82175063 100644 --- a/library/std/src/sys_common/mod.rs +++ b/library/std/src/sys_common/mod.rs @@ -46,6 +46,7 @@ cfg_if::cfg_if! { if #[cfg(any(target_os = "l4re", feature = "restricted-std", all(target_family = "wasm", not(target_os = "emscripten")), + target_os = "xous", all(target_vendor = "fortanix", target_env = "sgx")))] { pub use crate::sys::net; } else { diff --git a/src/bootstrap/builder.rs b/src/bootstrap/builder.rs index 50f1007e1ff..46a62eed952 100644 --- a/src/bootstrap/builder.rs +++ b/src/bootstrap/builder.rs @@ -1640,7 +1640,10 @@ impl<'a> Builder<'a> { // flesh out rpath support more fully in the future. rustflags.arg("-Zosx-rpath-install-name"); Some(format!("-Wl,-rpath,@loader_path/../{libdir}")) - } else if !target.contains("windows") && !target.contains("aix") { + } else if !target.contains("windows") + && !target.contains("aix") + && !target.contains("xous") + { rustflags.arg("-Clink-args=-Wl,-z,origin"); Some(format!("-Wl,-rpath,$ORIGIN/../{libdir}")) } else { diff --git a/src/doc/rustdoc/src/SUMMARY.md b/src/doc/rustdoc/src/SUMMARY.md index 12a8b2b8db4..3b6883c0d55 100644 --- a/src/doc/rustdoc/src/SUMMARY.md +++ b/src/doc/rustdoc/src/SUMMARY.md @@ -4,6 +4,7 @@ - [Command-line arguments](command-line-arguments.md) - [How to read rustdoc output](how-to-read-rustdoc.md) - [In-doc settings](read-documentation/in-doc-settings.md) + - [Search](read-documentation/search.md) - [How to write documentation](how-to-write-documentation.md) - [What to include (and exclude)](write-documentation/what-to-include.md) - [The `#[doc]` attribute](write-documentation/the-doc-attribute.md) diff --git a/src/doc/rustdoc/src/how-to-read-rustdoc.md b/src/doc/rustdoc/src/how-to-read-rustdoc.md index cd6e29ffd66..dade62c5423 100644 --- a/src/doc/rustdoc/src/how-to-read-rustdoc.md +++ b/src/doc/rustdoc/src/how-to-read-rustdoc.md @@ -75,56 +75,11 @@ or the current item whose documentation is being displayed. ## The Theme Picker and Search Interface When viewing `rustdoc`'s output in a browser with JavaScript enabled, -a dynamic interface appears at the top of the page composed of the search -interface, help screen, and options. - -### The Search Interface - -Typing in the search bar instantly searches the available documentation for -the string entered with a fuzzy matching algorithm that is tolerant of minor -typos. - -By default, the search results given are "In Names", -meaning that the fuzzy match is made against the names of items. -Matching names are shown on the left, and the first few words of their -descriptions are given on the right. -By clicking an item, you will navigate to its particular documentation. - -There are two other sets of results, shown as tabs in the search results pane. -"In Parameters" shows matches for the string in the types of parameters to -functions, and "In Return Types" shows matches in the return types of functions. -Both are very useful when looking for a function whose name you can't quite -bring to mind when you know the type you have or want. - -Names in the search interface can be prefixed with an item type followed by a -colon (such as `mod:`) to restrict the results to just that kind of item. Also, -searching for `println!` will search for a macro named `println`, just like -searching for `macro:println` does. - -Function signature searches can query generics, wrapped in angle brackets, and -traits are normalized like types in the search engine. For example, a function -with the signature `fn my_function<I: Iterator<Item=u32>>(input: I) -> usize` -can be matched with the following queries: - -* `Iterator<u32> -> usize` -* `trait:Iterator<primitive:u32> -> primitive:usize` -* `Iterator -> usize` - -Generics and function parameters are order-agnostic, but sensitive to nesting -and number of matches. For example, a function with the signature -`fn read_all(&mut self: impl Read) -> Result<Vec<u8>, Error>` -will match these queries: - -* `Read -> Result<Vec<u8>, Error>` -* `Read -> Result<Error, Vec>` -* `Read -> Result<Vec<u8>>` - -But it *does not* match `Result<Vec, u8>` or `Result<u8<Vec>>`. - -Function signature searches also support arrays and slices. The explicit name -`primitive:slice<u8>` and `primitive:array<u8>` can be used to match a slice -or array of bytes, while square brackets `[u8]` will match either one. Empty -square brackets, `[]`, will match any slice regardless of what it contains. +a dynamic interface appears at the top of the page composed of the [search] +interface, help screen, and [options]. + +[options]: read-documentation/in-doc-settings.html +[search]: read-documentation/search.md Paths are supported as well, you can look for `Vec::new` or `Option::Some` or even `module::module_child::another_child::struct::field`. Whitespace characters diff --git a/src/doc/rustdoc/src/read-documentation/search.md b/src/doc/rustdoc/src/read-documentation/search.md new file mode 100644 index 00000000000..56a5016d0ce --- /dev/null +++ b/src/doc/rustdoc/src/read-documentation/search.md @@ -0,0 +1,237 @@ +# Rustdoc search + +Typing in the search bar instantly searches the available documentation, +matching either the name and path of an item, or a function's approximate +type signature. + +## Search By Name + +To search by the name of an item (items include modules, types, traits, +functions, and macros), write its name or path. As a special case, the parts +of a path that normally get divided by `::` double colons can instead be +separated by spaces. For example: + + * [`vec new`] and [`vec::new`] both show the function `std::vec::Vec::new` + as a result. + * [`vec`], [`vec vec`], [`std::vec`], and [`std::vec::Vec`] all include the struct + `std::vec::Vec` itself in the results (and all but the last one also + include the module in the results). + +[`vec new`]: ../../std/vec/struct.Vec.html?search=vec%20new&filter-crate=std +[`vec::new`]: ../../std/vec/struct.Vec.html?search=vec::new&filter-crate=std +[`vec`]: ../../std/vec/struct.Vec.html?search=vec&filter-crate=std +[`vec vec`]: ../../std/vec/struct.Vec.html?search=vec%20vec&filter-crate=std +[`std::vec`]: ../../std/vec/struct.Vec.html?search=std::vec&filter-crate=std +[`std::vec::Vec`]: ../../std/vec/struct.Vec.html?search=std::vec::Vec&filter-crate=std +[`std::vec::Vec`]: ../../std/vec/struct.Vec.html?search=std::vec::Vec&filter-crate=std + +As a quick way to trim down the list of results, there's a drop-down selector +below the search input, labeled "Results in \[std\]". Clicking it can change +which crate is being searched. + +Rustdoc uses a fuzzy matching function that can tolerate typos for this, +though it's based on the length of the name that's typed in, so a good example +of how this works would be [`HahsMap`]. To avoid this, wrap the item in quotes, +searching for `"HahsMap"` (in this example, no results will be returned). + +[`HahsMap`]: ../../std/collections/struct.HashMap.html?search=HahsMap&filter-crate=std + +### Tabs in the Search By Name interface + +In fact, using [`HahsMap`] again as the example, it tells you that you're +using "In Names" by default, but also lists two other tabs below the crate +drop-down: "In Parameters" and "In Return Types". + +These two tabs are lists of functions, defined on the closest matching type +to the search (for `HahsMap`, it loudly auto-corrects to `hashmap`). This +auto-correct only kicks in if nothing is found that matches the literal. + +These tabs are not just methods. For example, searching the alloc crate for +[`Layout`] also lists functions that accept layouts even though they're +methods on the allocator or free functions. + +[`Layout`]: ../../alloc/index.html?search=Layout&filter-crate=alloc + +## Searching By Type Signature for functions + +If you know more specifically what the function you want to look at does, +Rustdoc can search by more than one type at once in the parameters and return +value. Multiple parameters are separated by `,` commas, and the return value +is written with after a `->` arrow. + +Before describing the syntax in more detail, here's a few sample searches of +the standard library and functions that are included in the results list: + +| Query | Results | +|-------|--------| +| [`usize -> vec`][] | `slice::repeat` and `Vec::with_capacity` | +| [`vec, vec -> bool`][] | `Vec::eq` | +| [`option<T>, fnonce -> option<U>`][] | `Option::map` and `Option::and_then` | +| [`option<T>, fnonce -> option<T>`][] | `Option::filter` and `Option::inspect` | +| [`option -> default`][] | `Option::unwrap_or_default` | +| [`stdout, [u8]`][stdoutu8] | `Stdout::write` | +| [`any -> !`][] | `panic::panic_any` | +| [`vec::intoiter<T> -> [T]`][iterasslice] | `IntoIter::as_slice` and `IntoIter::next_chunk` | + +[`usize -> vec`]: ../../std/vec/struct.Vec.html?search=usize%20-%3E%20vec&filter-crate=std +[`vec, vec -> bool`]: ../../std/vec/struct.Vec.html?search=vec,%20vec%20-%3E%20bool&filter-crate=std +[`option<T>, fnonce -> option<U>`]: ../../std/vec/struct.Vec.html?search=option<T>%2C%20fnonce%20->%20option<U>&filter-crate=std +[`option<T>, fnonce -> option<T>`]: ../../std/vec/struct.Vec.html?search=option<T>%2C%20fnonce%20->%20option<T>&filter-crate=std +[`option -> default`]: ../../std/vec/struct.Vec.html?search=option%20-%3E%20default&filter-crate=std +[`any -> !`]: ../../std/vec/struct.Vec.html?search=any%20-%3E%20!&filter-crate=std +[stdoutu8]: ../../std/vec/struct.Vec.html?search=stdout%2C%20[u8]&filter-crate=std +[iterasslice]: ../../std/vec/struct.Vec.html?search=vec%3A%3Aintoiter<T>%20->%20[T]&filter-crate=std + +### How type-based search works + +In a complex type-based search, Rustdoc always treats every item's name as literal. +If a name is used and nothing in the docs matches the individual item, such as +a typo-ed [`uize -> vec`][] search, the item `uize` is treated as a generic +type parameter (resulting in `vec::from` and other generic vec constructors). + +[`uize -> vec`]: ../../std/vec/struct.Vec.html?search=uize%20-%3E%20vec&filter-crate=std + +After deciding which items are type parameters and which are actual types, it +then searches by matching up the function parameters (written before the `->`) +and the return types (written after the `->`). Type matching is order-agnostic, +and allows items to be left out of the query, but items that are present in the +query must be present in the function for it to match. + +Function signature searches can query generics, wrapped in angle brackets, and +traits will be normalized like types in the search engine if no type parameters +match them. For example, a function with the signature +`fn my_function<I: Iterator<Item=u32>>(input: I) -> usize` +can be matched with the following queries: + +* `Iterator<u32> -> usize` +* `Iterator -> usize` + +Generics and function parameters are order-agnostic, but sensitive to nesting +and number of matches. For example, a function with the signature +`fn read_all(&mut self: impl Read) -> Result<Vec<u8>, Error>` +will match these queries: + +* `Read -> Result<Vec<u8>, Error>` +* `Read -> Result<Error, Vec>` +* `Read -> Result<Vec<u8>>` + +But it *does not* match `Result<Vec, u8>` or `Result<u8<Vec>>`. + +Function signature searches also support arrays and slices. The explicit name +`primitive:slice<u8>` and `primitive:array<u8>` can be used to match a slice +or array of bytes, while square brackets `[u8]` will match either one. Empty +square brackets, `[]`, will match any slice or array regardless of what +it contains, while a slice with a type parameter, like `[T]`, will only match +functions that actually operate on generic slices. + +### Limitations and quirks of type-based search + +Type-based search is still a buggy, experimental, work-in-progress feature. +Most of these limitations should be addressed in future version of Rustdoc. + + * There's no way to write trait constraints on generic parameters. + You can name traits directly, and if there's a type parameter + with that bound, it'll match, but `option<T> -> T where T: Default` + cannot be precisely searched for (use `option<Default> -> Default`). + + * Type parameters match type parameters, such that `Option<A>` matches + `Option<T>`, but never match concrete types in function signatures. + A trait named as if it were a type, such as `Option<Read>`, will match + a type parameter constrained by that trait, such as + `Option<T> where T: Read`, as well as matching `dyn Trait` and + `impl Trait`. + + * `impl Trait` in argument position is treated exactly like a type + parameter, but in return position it will not match type parameters. + + * Any type named in a complex type-based search will be assumed to be a + type parameter if nothing matching the name exactly is found. If you + want to force a type parameter, write `generic:T` and it will be used + as a type parameter even if a matching name is found. If you know + that you don't want a type parameter, you can force it to match + something else by giving it a different prefix like `struct:T`. + + * It's impossible to search for references, pointers, or tuples. The + wrapped types can be searched for, so a function that takes `&File` can + be found with `File`, but you'll get a parse error when typing an `&` + into the search field. Similarly, `Option<(T, U)>` can be matched with + `Option<T, U>`, but `(` will give a parse error. + + * Searching for lifetimes is not supported. + + * It's impossible to search for closures based on their parameters or + return values. + + * It's impossible to search based on the length of an array. + +## Item filtering + +Names in the search interface can be prefixed with an item type followed by a +colon (such as `mod:`) to restrict the results to just that kind of item. Also, +searching for `println!` will search for a macro named `println`, just like +searching for `macro:println` does. The complete list of available filters is +given under the <kbd>?</kbd> Help area, and in the detailed syntax below. + +Item filters can be used in both name-based and type signature-based searches. + +## Search query syntax + +```text +ident = *(ALPHA / DIGIT / "_") +path = ident *(DOUBLE-COLON ident) [!] +slice = OPEN-SQUARE-BRACKET [ nonempty-arg-list ] CLOSE-SQUARE-BRACKET +arg = [type-filter *WS COLON *WS] (path [generics] / slice / [!]) +type-sep = COMMA/WS *(COMMA/WS) +nonempty-arg-list = *(type-sep) arg *(type-sep arg) *(type-sep) +generics = OPEN-ANGLE-BRACKET [ nonempty-arg-list ] *(type-sep) + CLOSE-ANGLE-BRACKET +return-args = RETURN-ARROW *(type-sep) nonempty-arg-list + +exact-search = [type-filter *WS COLON] [ RETURN-ARROW ] *WS QUOTE ident QUOTE [ generics ] +type-search = [ nonempty-arg-list ] [ return-args ] + +query = *WS (exact-search / type-search) *WS + +type-filter = ( + "mod" / + "externcrate" / + "import" / + "struct" / + "enum" / + "fn" / + "type" / + "static" / + "trait" / + "impl" / + "tymethod" / + "method" / + "structfield" / + "variant" / + "macro" / + "primitive" / + "associatedtype" / + "constant" / + "associatedconstant" / + "union" / + "foreigntype" / + "keyword" / + "existential" / + "attr" / + "derive" / + "traitalias" / + "generic") + +OPEN-ANGLE-BRACKET = "<" +CLOSE-ANGLE-BRACKET = ">" +OPEN-SQUARE-BRACKET = "[" +CLOSE-SQUARE-BRACKET = "]" +COLON = ":" +DOUBLE-COLON = "::" +QUOTE = %x22 +COMMA = "," +RETURN-ARROW = "->" + +ALPHA = %x41-5A / %x61-7A ; A-Z / a-z +DIGIT = %x30-39 +WS = %x09 / " " +``` diff --git a/src/librustdoc/clean/types.rs b/src/librustdoc/clean/types.rs index b276745f317..ef7794cc41e 100644 --- a/src/librustdoc/clean/types.rs +++ b/src/librustdoc/clean/types.rs @@ -1639,10 +1639,6 @@ impl Type { matches!(self, Type::Generic(_)) } - pub(crate) fn is_impl_trait(&self) -> bool { - matches!(self, Type::ImplTrait(_)) - } - pub(crate) fn is_unit(&self) -> bool { matches!(self, Type::Tuple(v) if v.is_empty()) } diff --git a/src/librustdoc/html/render/mod.rs b/src/librustdoc/html/render/mod.rs index f70f59d3be3..3e671a64b54 100644 --- a/src/librustdoc/html/render/mod.rs +++ b/src/librustdoc/html/render/mod.rs @@ -101,7 +101,7 @@ pub(crate) struct IndexItem { pub(crate) path: String, pub(crate) desc: String, pub(crate) parent: Option<DefId>, - pub(crate) parent_idx: Option<usize>, + pub(crate) parent_idx: Option<isize>, pub(crate) search_type: Option<IndexItemFunctionType>, pub(crate) aliases: Box<[Symbol]>, pub(crate) deprecation: Option<Deprecation>, @@ -122,7 +122,10 @@ impl Serialize for RenderType { let id = match &self.id { // 0 is a sentinel, everything else is one-indexed None => 0, - Some(RenderTypeId::Index(idx)) => idx + 1, + // concrete type + Some(RenderTypeId::Index(idx)) if *idx >= 0 => idx + 1, + // generic type parameter + Some(RenderTypeId::Index(idx)) => *idx, _ => panic!("must convert render types to indexes before serializing"), }; if let Some(generics) = &self.generics { @@ -140,7 +143,7 @@ impl Serialize for RenderType { pub(crate) enum RenderTypeId { DefId(DefId), Primitive(clean::PrimitiveType), - Index(usize), + Index(isize), } /// Full type of functions/methods in the search index. @@ -148,6 +151,7 @@ pub(crate) enum RenderTypeId { pub(crate) struct IndexItemFunctionType { inputs: Vec<RenderType>, output: Vec<RenderType>, + where_clause: Vec<Vec<RenderType>>, } impl Serialize for IndexItemFunctionType { @@ -170,10 +174,17 @@ impl Serialize for IndexItemFunctionType { _ => seq.serialize_element(&self.inputs)?, } match &self.output[..] { - [] => {} + [] if self.where_clause.is_empty() => {} [one] if one.generics.is_none() => seq.serialize_element(one)?, _ => seq.serialize_element(&self.output)?, } + for constraint in &self.where_clause { + if let [one] = &constraint[..] && one.generics.is_none() { + seq.serialize_element(one)?; + } else { + seq.serialize_element(constraint)?; + } + } seq.end() } } diff --git a/src/librustdoc/html/render/search_index.rs b/src/librustdoc/html/render/search_index.rs index 145c7d18dd0..78c443b2257 100644 --- a/src/librustdoc/html/render/search_index.rs +++ b/src/librustdoc/html/render/search_index.rs @@ -68,16 +68,16 @@ pub(crate) fn build_index<'tcx>( // Reduce `DefId` in paths into smaller sequential numbers, // and prune the paths that do not appear in the index. let mut lastpath = ""; - let mut lastpathid = 0usize; + let mut lastpathid = 0isize; // First, on function signatures let mut search_index = std::mem::replace(&mut cache.search_index, Vec::new()); for item in search_index.iter_mut() { fn insert_into_map<F: std::hash::Hash + Eq>( ty: &mut RenderType, - map: &mut FxHashMap<F, usize>, + map: &mut FxHashMap<F, isize>, itemid: F, - lastpathid: &mut usize, + lastpathid: &mut isize, crate_paths: &mut Vec<(ItemType, Vec<Symbol>)>, item_type: ItemType, path: &[Symbol], @@ -97,9 +97,9 @@ pub(crate) fn build_index<'tcx>( fn convert_render_type( ty: &mut RenderType, cache: &mut Cache, - itemid_to_pathid: &mut FxHashMap<ItemId, usize>, - primitives: &mut FxHashMap<Symbol, usize>, - lastpathid: &mut usize, + itemid_to_pathid: &mut FxHashMap<ItemId, isize>, + primitives: &mut FxHashMap<Symbol, isize>, + lastpathid: &mut isize, crate_paths: &mut Vec<(ItemType, Vec<Symbol>)>, ) { if let Some(generics) = &mut ty.generics { @@ -173,6 +173,18 @@ pub(crate) fn build_index<'tcx>( &mut crate_paths, ); } + for constraint in &mut search_type.where_clause { + for trait_ in &mut constraint[..] { + convert_render_type( + trait_, + cache, + &mut itemid_to_pathid, + &mut primitives, + &mut lastpathid, + &mut crate_paths, + ); + } + } } } @@ -402,7 +414,7 @@ pub(crate) fn get_function_type_for_search<'tcx>( impl_generics: Option<&(clean::Type, clean::Generics)>, cache: &Cache, ) -> Option<IndexItemFunctionType> { - let (mut inputs, mut output) = match *item.kind { + let (mut inputs, mut output, where_clause) = match *item.kind { clean::FunctionItem(ref f) => get_fn_inputs_and_outputs(f, tcx, impl_generics, cache), clean::MethodItem(ref m, _) => get_fn_inputs_and_outputs(m, tcx, impl_generics, cache), clean::TyMethodItem(ref m) => get_fn_inputs_and_outputs(m, tcx, impl_generics, cache), @@ -412,7 +424,7 @@ pub(crate) fn get_function_type_for_search<'tcx>( inputs.retain(|a| a.id.is_some() || a.generics.is_some()); output.retain(|a| a.id.is_some() || a.generics.is_some()); - Some(IndexItemFunctionType { inputs, output }) + Some(IndexItemFunctionType { inputs, output, where_clause }) } fn get_index_type(clean_type: &clean::Type, generics: Vec<RenderType>) -> RenderType { @@ -432,96 +444,48 @@ fn get_index_type_id(clean_type: &clean::Type) -> Option<RenderTypeId> { clean::BorrowedRef { ref type_, .. } | clean::RawPointer(_, ref type_) => { get_index_type_id(type_) } - // The type parameters are converted to generics in `add_generics_and_bounds_as_types` + // The type parameters are converted to generics in `simplify_fn_type` clean::Slice(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Slice)), clean::Array(_, _) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Array)), + clean::Tuple(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Tuple)), // Not supported yet clean::BareFunction(_) | clean::Generic(_) | clean::ImplTrait(_) - | clean::Tuple(_) | clean::QPath { .. } | clean::Infer => None, } } -/// The point of this function is to replace bounds with types. +#[derive(Clone, Copy, Eq, Hash, PartialEq)] +enum SimplifiedParam { + // other kinds of type parameters are identified by their name + Symbol(Symbol), + // every argument-position impl trait is its own type parameter + Anonymous(isize), +} + +/// The point of this function is to lower generics and types into the simplified form that the +/// frontend search engine can use. /// -/// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return -/// `[Display, Option]`. If a type parameter has no trait bound, it is discarded. +/// For example, `[T, U, i32]]` where you have the bounds: `T: Display, U: Option<T>` will return +/// `[-1, -2, i32] where -1: Display, -2: Option<-1>`. If a type parameter has no traid bound, it +/// will still get a number. If a constraint is present but not used in the actual types, it will +/// not be added to the map. /// -/// Important note: It goes through generics recursively. So if you have -/// `T: Option<Result<(), ()>>`, it'll go into `Option` and then into `Result`. -#[instrument(level = "trace", skip(tcx, res, cache))] -fn add_generics_and_bounds_as_types<'tcx, 'a>( +/// This function also works recursively. +#[instrument(level = "trace", skip(tcx, res, rgen, cache))] +fn simplify_fn_type<'tcx, 'a>( self_: Option<&'a Type>, generics: &Generics, arg: &'a Type, tcx: TyCtxt<'tcx>, recurse: usize, res: &mut Vec<RenderType>, + rgen: &mut FxHashMap<SimplifiedParam, (isize, Vec<RenderType>)>, + is_return: bool, cache: &Cache, ) { - fn insert_ty(res: &mut Vec<RenderType>, ty: Type, mut generics: Vec<RenderType>) { - // generics and impl trait are both identified by their generics, - // rather than a type name itself - let anonymous = ty.is_full_generic() || ty.is_impl_trait(); - let generics_empty = generics.is_empty(); - - if anonymous { - if generics_empty { - // This is a type parameter with no trait bounds (for example: `T` in - // `fn f<T>(p: T)`, so not useful for the rustdoc search because we would end up - // with an empty type with an empty name. Let's just discard it. - return; - } else if generics.len() == 1 { - // In this case, no need to go through an intermediate state if the type parameter - // contains only one trait bound. - // - // For example: - // - // `fn foo<T: Display>(r: Option<T>) {}` - // - // In this case, it would contain: - // - // ``` - // [{ - // name: "option", - // generics: [{ - // name: "", - // generics: [ - // name: "Display", - // generics: [] - // }] - // }] - // }] - // ``` - // - // After removing the intermediate (unnecessary) type parameter, it'll become: - // - // ``` - // [{ - // name: "option", - // generics: [{ - // name: "Display", - // generics: [] - // }] - // }] - // ``` - // - // To be noted that it can work if there is ONLY ONE trait bound, otherwise we still - // need to keep it as is! - res.push(generics.pop().unwrap()); - return; - } - } - let index_ty = get_index_type(&ty, generics); - if index_ty.id.is_none() && generics_empty { - return; - } - res.push(index_ty); - } - if recurse >= 10 { // FIXME: remove this whole recurse thing when the recursion bug is fixed // See #59502 for the original issue. @@ -548,88 +512,126 @@ fn add_generics_and_bounds_as_types<'tcx, 'a>( // for its bounds. if let Type::Generic(arg_s) = *arg { // First we check if the bounds are in a `where` predicate... + let mut type_bounds = Vec::new(); for where_pred in generics.where_predicates.iter().filter(|g| match g { WherePredicate::BoundPredicate { ty: Type::Generic(ty_s), .. } => *ty_s == arg_s, _ => false, }) { - let mut ty_generics = Vec::new(); let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]); for bound in bounds.iter() { if let Some(path) = bound.get_trait_path() { let ty = Type::Path { path }; - add_generics_and_bounds_as_types( + simplify_fn_type( self_, generics, &ty, tcx, recurse + 1, - &mut ty_generics, + &mut type_bounds, + rgen, + is_return, cache, ); } } - insert_ty(res, arg.clone(), ty_generics); } // Otherwise we check if the trait bounds are "inlined" like `T: Option<u32>`... if let Some(bound) = generics.params.iter().find(|g| g.is_type() && g.name == arg_s) { - let mut ty_generics = Vec::new(); for bound in bound.get_bounds().unwrap_or(&[]) { if let Some(path) = bound.get_trait_path() { let ty = Type::Path { path }; - add_generics_and_bounds_as_types( + simplify_fn_type( self_, generics, &ty, tcx, recurse + 1, - &mut ty_generics, + &mut type_bounds, + rgen, + is_return, cache, ); } } - insert_ty(res, arg.clone(), ty_generics); + } + if let Some((idx, _)) = rgen.get(&SimplifiedParam::Symbol(arg_s)) { + res.push(RenderType { id: Some(RenderTypeId::Index(*idx)), generics: None }); + } else { + let idx = -isize::try_from(rgen.len() + 1).unwrap(); + rgen.insert(SimplifiedParam::Symbol(arg_s), (idx, type_bounds)); + res.push(RenderType { id: Some(RenderTypeId::Index(idx)), generics: None }); } } else if let Type::ImplTrait(ref bounds) = *arg { - let mut ty_generics = Vec::new(); + let mut type_bounds = Vec::new(); for bound in bounds { if let Some(path) = bound.get_trait_path() { let ty = Type::Path { path }; - add_generics_and_bounds_as_types( + simplify_fn_type( self_, generics, &ty, tcx, recurse + 1, - &mut ty_generics, + &mut type_bounds, + rgen, + is_return, cache, ); } } - insert_ty(res, arg.clone(), ty_generics); + if is_return && !type_bounds.is_empty() { + // In parameter position, `impl Trait` is a unique thing. + res.push(RenderType { id: None, generics: Some(type_bounds) }); + } else { + // In parameter position, `impl Trait` is the same as an unnamed generic parameter. + let idx = -isize::try_from(rgen.len() + 1).unwrap(); + rgen.insert(SimplifiedParam::Anonymous(idx), (idx, type_bounds)); + res.push(RenderType { id: Some(RenderTypeId::Index(idx)), generics: None }); + } } else if let Type::Slice(ref ty) = *arg { let mut ty_generics = Vec::new(); - add_generics_and_bounds_as_types( + simplify_fn_type( self_, generics, &ty, tcx, recurse + 1, &mut ty_generics, + rgen, + is_return, cache, ); - insert_ty(res, arg.clone(), ty_generics); + res.push(get_index_type(arg, ty_generics)); } else if let Type::Array(ref ty, _) = *arg { let mut ty_generics = Vec::new(); - add_generics_and_bounds_as_types( + simplify_fn_type( self_, generics, &ty, tcx, recurse + 1, &mut ty_generics, + rgen, + is_return, cache, ); - insert_ty(res, arg.clone(), ty_generics); + res.push(get_index_type(arg, ty_generics)); + } else if let Type::Tuple(ref tys) = *arg { + let mut ty_generics = Vec::new(); + for ty in tys { + simplify_fn_type( + self_, + generics, + &ty, + tcx, + recurse + 1, + &mut ty_generics, + rgen, + is_return, + cache, + ); + } + res.push(get_index_type(arg, ty_generics)); } else { // This is not a type parameter. So for example if we have `T, U: Option<T>`, and we're // looking at `Option`, we enter this "else" condition, otherwise if it's `T`, we don't. @@ -639,18 +641,26 @@ fn add_generics_and_bounds_as_types<'tcx, 'a>( let mut ty_generics = Vec::new(); if let Some(arg_generics) = arg.generics() { for gen in arg_generics.iter() { - add_generics_and_bounds_as_types( + simplify_fn_type( self_, generics, gen, tcx, recurse + 1, &mut ty_generics, + rgen, + is_return, cache, ); } } - insert_ty(res, arg.clone(), ty_generics); + let id = get_index_type_id(&arg); + if id.is_some() || !ty_generics.is_empty() { + res.push(RenderType { + id, + generics: if ty_generics.is_empty() { None } else { Some(ty_generics) }, + }); + } } } @@ -663,7 +673,7 @@ fn get_fn_inputs_and_outputs<'tcx>( tcx: TyCtxt<'tcx>, impl_generics: Option<&(clean::Type, clean::Generics)>, cache: &Cache, -) -> (Vec<RenderType>, Vec<RenderType>) { +) -> (Vec<RenderType>, Vec<RenderType>, Vec<Vec<RenderType>>) { let decl = &func.decl; let combined_generics; @@ -689,21 +699,27 @@ fn get_fn_inputs_and_outputs<'tcx>( (None, &func.generics) }; - let mut all_types = Vec::new(); + let mut rgen: FxHashMap<SimplifiedParam, (isize, Vec<RenderType>)> = Default::default(); + + let mut arg_types = Vec::new(); for arg in decl.inputs.values.iter() { - let mut args = Vec::new(); - add_generics_and_bounds_as_types(self_, generics, &arg.type_, tcx, 0, &mut args, cache); - if !args.is_empty() { - all_types.extend(args); - } else { - all_types.push(get_index_type(&arg.type_, vec![])); - } + simplify_fn_type( + self_, + generics, + &arg.type_, + tcx, + 0, + &mut arg_types, + &mut rgen, + false, + cache, + ); } let mut ret_types = Vec::new(); - add_generics_and_bounds_as_types(self_, generics, &decl.output, tcx, 0, &mut ret_types, cache); - if ret_types.is_empty() { - ret_types.push(get_index_type(&decl.output, vec![])); - } - (all_types, ret_types) + simplify_fn_type(self_, generics, &decl.output, tcx, 0, &mut ret_types, &mut rgen, true, cache); + + let mut simplified_params = rgen.into_values().collect::<Vec<_>>(); + simplified_params.sort_by_key(|(idx, _)| -idx); + (arg_types, ret_types, simplified_params.into_iter().map(|(_idx, traits)| traits).collect()) } diff --git a/src/librustdoc/html/static/js/externs.js b/src/librustdoc/html/static/js/externs.js index f697abd0776..c7811b43d16 100644 --- a/src/librustdoc/html/static/js/externs.js +++ b/src/librustdoc/html/static/js/externs.js @@ -9,7 +9,7 @@ function initSearch(searchIndex){} /** * @typedef {{ * name: string, - * id: integer, + * id: integer|null, * fullPath: Array<string>, * pathWithoutLast: Array<string>, * pathLast: string, @@ -37,6 +37,7 @@ let ParserState; * args: Array<QueryElement>, * returned: Array<QueryElement>, * foundElems: number, + * totalElems: number, * literalSearch: boolean, * corrections: Array<{from: string, to: integer}>, * }} @@ -103,7 +104,7 @@ let ResultObject; * * fn something() -> Result<usize, usize> * - * If output was allowed to be any RawFunctionType, it would look like this + * If output was allowed to be any RawFunctionType, it would look like thi * * [[], [50, [3, 3]]] * @@ -113,10 +114,56 @@ let ResultObject; * in favor of the pair of types interpretation. This is why the `(number|Array<RawFunctionType>)` * is used instead of `(RawFunctionType|Array<RawFunctionType>)`. * + * The output can be skipped if it's actually unit and there's no type constraints. If thi + * function accepts constrained generics, then the output will be unconditionally emitted, and + * after it will come a list of trait constraints. The position of the item in the list will + * determine which type parameter it is. For example: + * + * [1, 2, 3, 4, 5] + * ^ ^ ^ ^ ^ + * | | | | - generic parameter (-3) of trait 5 + * | | | - generic parameter (-2) of trait 4 + * | | - generic parameter (-1) of trait 3 + * | - this function returns a single value (type 2) + * - this function takes a single input parameter (type 1) + * + * Or, for a less contrived version: + * + * [[[4, -1], 3], [[5, -1]], 11] + * -^^^^^^^---- ^^^^^^^ ^^ + * | | | - generic parameter, roughly `where -1: 11` + * | | | since -1 is the type parameter and 11 the trait + * | | - function output 5<-1> + * | - the overall function signature is something like + * | `fn(4<-1>, 3) -> 5<-1> where -1: 11` + * - function input, corresponds roughly to 4<-1> + * 4 is an index into the `p` array for a type + * -1 is the generic parameter, given by 11 + * + * If a generic parameter has multiple trait constraints, it gets wrapped in an array, just like + * function inputs and outputs: + * + * [-1, -1, [4, 3]] + * ^^^^^^ where -1: 4 + 3 + * + * If a generic parameter's trait constraint has generic parameters, it gets wrapped in the array + * even if only one exists. In other words, the ambiguity of `4<3>` and `4 + 3` is resolved in + * favor of `4 + 3`: + * + * [-1, -1, [[4, 3]]] + * ^^^^^^^^ where -1: 4 + 3 + * + * [-1, -1, [5, [4, 3]]] + * ^^^^^^^^^^^ where -1: 5, -2: 4 + 3 + * + * If a generic parameter has no trait constraints (like in Rust, the `Sized` constraint i + * implied and a fake `?Sized` constraint used to note its absence), it will be filled in with 0. + * * @typedef {( * 0 | * [(number|Array<RawFunctionType>)] | - * [(number|Array<RawFunctionType>), (number|Array<RawFunctionType>)] + * [(number|Array<RawFunctionType>), (number|Array<RawFunctionType>)] | + * Array<(number|Array<RawFunctionType>)> * )} */ let RawFunctionSearchType; @@ -136,6 +183,7 @@ let RawFunctionType; * @typedef {{ * inputs: Array<FunctionType>, * output: Array<FunctionType>, + * where_clause: Array<Array<FunctionType>>, * }} */ let FunctionSearchType; diff --git a/src/librustdoc/html/static/js/search.js b/src/librustdoc/html/static/js/search.js index 0e270bbcc40..407bf5f2c5f 100644 --- a/src/librustdoc/html/static/js/search.js +++ b/src/librustdoc/html/static/js/search.js @@ -3,6 +3,17 @@ "use strict"; +// polyfill +// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/toSpliced +if (!Array.prototype.toSpliced) { + // Can't use arrow functions, because we want `this` + Array.prototype.toSpliced = function() { + const me = this.slice(); + Array.prototype.splice.apply(me, arguments); + return me; + }; +} + (function() { // This mapping table should match the discriminants of // `rustdoc::formats::item_type::ItemType` type in Rust. @@ -33,6 +44,7 @@ const itemTypes = [ "attr", "derive", "traitalias", + "generic", ]; const longItemTypes = [ @@ -67,6 +79,7 @@ const longItemTypes = [ // used for special search precedence const TY_PRIMITIVE = itemTypes.indexOf("primitive"); const TY_KEYWORD = itemTypes.indexOf("keyword"); +const TY_GENERIC = itemTypes.indexOf("generic"); const ROOT_PATH = typeof window !== "undefined" ? window.rootPath : "../"; function hasOwnPropertyRustdoc(obj, property) { @@ -252,7 +265,7 @@ function initSearch(rawSearchIndex) { /** * 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 -1 (pure generic). + * 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 @@ -264,7 +277,7 @@ function initSearch(rawSearchIndex) { */ function buildTypeMapIndex(name) { if (name === "" || name === null) { - return -1; + return null; } if (typeNameIdMap.has(name)) { @@ -489,7 +502,7 @@ function initSearch(rawSearchIndex) { } return { name: "never", - id: -1, + id: null, fullPath: ["never"], pathWithoutLast: [], pathLast: "never", @@ -531,7 +544,7 @@ function initSearch(rawSearchIndex) { } return { name: name.trim(), - id: -1, + id: null, fullPath: pathSegments, pathWithoutLast: pathSegments.slice(0, pathSegments.length - 1), pathLast: pathSegments[pathSegments.length - 1], @@ -660,7 +673,7 @@ function initSearch(rawSearchIndex) { } elems.push({ name: "[]", - id: -1, + id: null, fullPath: ["[]"], pathWithoutLast: [], pathLast: "[]", @@ -971,9 +984,13 @@ function initSearch(rawSearchIndex) { 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, }; } @@ -1014,64 +1031,10 @@ function initSearch(rawSearchIndex) { /** * Parses the query. * - * The supported syntax by this parser is as follow: - * - * ident = *(ALPHA / DIGIT / "_") - * path = ident *(DOUBLE-COLON/{WS} ident) [!] - * slice = OPEN-SQUARE-BRACKET [ nonempty-arg-list ] CLOSE-SQUARE-BRACKET - * arg = [type-filter *WS COLON *WS] (path [generics] / slice) - * type-sep = *WS COMMA *(COMMA) - * nonempty-arg-list = *(type-sep) arg *(type-sep arg) *(type-sep) - * generics = OPEN-ANGLE-BRACKET [ nonempty-arg-list ] *(type-sep) - * CLOSE-ANGLE-BRACKET - * return-args = RETURN-ARROW *(type-sep) nonempty-arg-list - * - * exact-search = [type-filter *WS COLON] [ RETURN-ARROW ] *WS QUOTE ident QUOTE [ generics ] - * type-search = [ nonempty-arg-list ] [ return-args ] - * - * query = *WS (exact-search / type-search) *WS - * - * type-filter = ( - * "mod" / - * "externcrate" / - * "import" / - * "struct" / - * "enum" / - * "fn" / - * "type" / - * "static" / - * "trait" / - * "impl" / - * "tymethod" / - * "method" / - * "structfield" / - * "variant" / - * "macro" / - * "primitive" / - * "associatedtype" / - * "constant" / - * "associatedconstant" / - * "union" / - * "foreigntype" / - * "keyword" / - * "existential" / - * "attr" / - * "derive" / - * "traitalias") + * The supported syntax by this parser is given in the rustdoc book chapter + * /src/doc/rustdoc/src/read-documentation/search.md * - * OPEN-ANGLE-BRACKET = "<" - * CLOSE-ANGLE-BRACKET = ">" - * OPEN-SQUARE-BRACKET = "[" - * CLOSE-SQUARE-BRACKET = "]" - * COLON = ":" - * DOUBLE-COLON = "::" - * QUOTE = %x22 - * COMMA = "," - * RETURN-ARROW = "->" - * - * ALPHA = %x41-5A / %x61-7A ; A-Z / a-z - * DIGIT = %x30-39 - * WS = %x09 / " " + * When adding new things to the parser, add them there, too! * * @param {string} val - The user query * @@ -1124,6 +1087,7 @@ function initSearch(rawSearchIndex) { query.literalSearch = parserState.totalElems > 1; } query.foundElems = query.elems.length + query.returned.length; + query.totalElems = parserState.totalElems; return query; } @@ -1172,7 +1136,7 @@ function initSearch(rawSearchIndex) { const out = []; for (const result of results) { - if (result.id > -1) { + if (result.id !== -1) { const obj = searchIndex[result.id]; obj.dist = result.dist; const res = buildHrefAndPath(obj); @@ -1348,192 +1312,311 @@ function initSearch(rawSearchIndex) { * This function checks generics in search query `queryElem` can all be found in the * search index (`fnType`), * - * @param {FunctionType} fnType - The object to check. - * @param {QueryElement} queryElem - The element from the parsed query. + * This function returns `true` if it matches, and also writes the results to mgensInout. + * It returns `false` if no match is found, and leaves mgensInout untouched. + * + * @param {FunctionType} fnType - The object to check. + * @param {QueryElement} queryElem - The element from the parsed query. + * @param {[FunctionType]} whereClause - Trait bounds for generic items. + * @param {Map<number,number>|null} mgensInout - Map functions generics to query generics. * * @return {boolean} - Returns true if a match, false otherwise. */ - function checkGenerics(fnType, queryElem) { - return unifyFunctionTypes(fnType.generics, queryElem.generics); + function checkGenerics(fnType, queryElem, whereClause, mgensInout) { + return unifyFunctionTypes( + fnType.generics, + queryElem.generics, + whereClause, + mgensInout, + mgens => { + if (mgensInout) { + for (const [fid, qid] of mgens.entries()) { + mgensInout.set(fid, qid); + } + } + return true; + } + ); } /** * This function checks if a list of search query `queryElems` can all be found in the * search index (`fnTypes`). * - * @param {Array<FunctionType>} fnTypes - The objects to check. + * This function returns `true` on a match, or `false` if none. If `solutionCb` is + * supplied, it will call that function with mgens, and that callback can accept or + * reject the result bu returning `true` or `false`. If the callback returns false, + * then this function will try with a different solution, or bail with false if it + * runs out of candidates. + * + * @param {Array<FunctionType>} fnTypes - The objects to check. * @param {Array<QueryElement>} queryElems - The elements from the parsed query. + * @param {[FunctionType]} whereClause - Trait bounds for generic items. + * @param {Map<number,number>|null} mgensIn + * - Map functions generics to query generics (never modified). + * @param {null|Map<number,number> -> bool} solutionCb - Called for each `mgens` solution. * * @return {boolean} - Returns true if a match, false otherwise. */ - function unifyFunctionTypes(fnTypes, queryElems) { - // This search engine implements order-agnostic unification. There - // should be no missing duplicates (generics have "bag semantics"), - // and the row is allowed to have extras. + function unifyFunctionTypes(fnTypesIn, queryElems, whereClause, mgensIn, solutionCb) { + /** + * @type Map<integer, integer> + */ + let mgens = new Map(mgensIn); if (queryElems.length === 0) { - return true; + return !solutionCb || solutionCb(mgens); } - if (!fnTypes || fnTypes.length === 0) { + if (!fnTypesIn || fnTypesIn.length === 0) { return false; } + const ql = queryElems.length; + let fl = fnTypesIn.length; /** - * @type Map<integer, QueryElement[]> + * @type Array<FunctionType> */ - const queryElemSet = new Map(); - const addQueryElemToQueryElemSet = queryElem => { - let currentQueryElemList; - if (queryElemSet.has(queryElem.id)) { - currentQueryElemList = queryElemSet.get(queryElem.id); - } else { - currentQueryElemList = []; - queryElemSet.set(queryElem.id, currentQueryElemList); - } - currentQueryElemList.push(queryElem); - }; - for (const queryElem of queryElems) { - addQueryElemToQueryElemSet(queryElem); - } + let fnTypes = fnTypesIn.slice(); /** - * @type Map<integer, FunctionType[]> + * loop works by building up a solution set in the working arrays + * fnTypes gets mutated in place to make this work, while queryElems + * is left alone + * + * vvvvvvv `i` points here + * queryElems = [ good, good, good, unknown, unknown ], + * fnTypes = [ good, good, good, unknown, unknown ], + * ---------------- ^^^^^^^^^^^^^^^^ `j` iterates after `i`, + * | looking for candidates + * everything before `i` is the + * current working solution + * + * Everything in the current working solution is known to be a good + * match, but it might not be the match we wind up going with, because + * there might be more than one candidate match, and we need to try them all + * before giving up. So, to handle this, it backtracks on failure. + * + * @type Array<{ + * "fnTypesScratch": Array<FunctionType>, + * "queryElemsOffset": integer, + * "fnTypesOffset": integer + * }> */ - const fnTypeSet = new Map(); - const addFnTypeToFnTypeSet = fnType => { - // Pure generic, or an item that's not matched by any query elems. - // Try [unboxing] it. - // - // [unboxing]: - // http://ndmitchell.com/downloads/slides-hoogle_fast_type_searching-09_aug_2008.pdf - const queryContainsArrayOrSliceElem = queryElemSet.has(typeNameIdOfArrayOrSlice); - if (fnType.id === -1 || !( - queryElemSet.has(fnType.id) || - (fnType.id === typeNameIdOfSlice && queryContainsArrayOrSliceElem) || - (fnType.id === typeNameIdOfArray && queryContainsArrayOrSliceElem) - )) { - for (const innerFnType of fnType.generics) { - addFnTypeToFnTypeSet(innerFnType); - } - return; - } - let currentQueryElemList = queryElemSet.get(fnType.id) || []; - let matchIdx = currentQueryElemList.findIndex(queryElem => { - return typePassesFilter(queryElem.typeFilter, fnType.ty) && - checkGenerics(fnType, queryElem); - }); - if (matchIdx === -1 && - (fnType.id === typeNameIdOfSlice || fnType.id === typeNameIdOfArray) && - queryContainsArrayOrSliceElem - ) { - currentQueryElemList = queryElemSet.get(typeNameIdOfArrayOrSlice) || []; - matchIdx = currentQueryElemList.findIndex(queryElem => { - return typePassesFilter(queryElem.typeFilter, fnType.ty) && - checkGenerics(fnType, queryElem); - }); - } - // None of the query elems match the function type. - // Try [unboxing] it. - if (matchIdx === -1) { - for (const innerFnType of fnType.generics) { - addFnTypeToFnTypeSet(innerFnType); + const backtracking = []; + let i = 0; + let j = 0; + const backtrack = () => { + while (backtracking.length !== 0) { + // this session failed, but there are other possible solutions + // to backtrack, reset to (a copy of) the old array, do the swap or unboxing + const { + fnTypesScratch, + mgensScratch, + queryElemsOffset, + fnTypesOffset, + unbox, + } = backtracking.pop(); + mgens = new Map(mgensScratch); + const fnType = fnTypesScratch[fnTypesOffset]; + const queryElem = queryElems[queryElemsOffset]; + if (unbox) { + if (fnType.id < 0) { + if (mgens.has(fnType.id) && mgens.get(fnType.id) !== 0) { + continue; + } + mgens.set(fnType.id, 0); + } + const generics = fnType.id < 0 ? + whereClause[(-fnType.id) - 1] : + fnType.generics; + fnTypes = fnTypesScratch.toSpliced(fnTypesOffset, 1, ...generics); + fl = fnTypes.length; + // re-run the matching algorithm on this item + i = queryElemsOffset - 1; + } else { + if (fnType.id < 0) { + if (mgens.has(fnType.id) && mgens.get(fnType.id) !== queryElem.id) { + continue; + } + mgens.set(fnType.id, queryElem.id); + } + fnTypes = fnTypesScratch.slice(); + fl = fnTypes.length; + const tmp = fnTypes[queryElemsOffset]; + fnTypes[queryElemsOffset] = fnTypes[fnTypesOffset]; + fnTypes[fnTypesOffset] = tmp; + // this is known as a good match; go to the next one + i = queryElemsOffset; } - return; - } - let currentFnTypeList; - if (fnTypeSet.has(fnType.id)) { - currentFnTypeList = fnTypeSet.get(fnType.id); - } else { - currentFnTypeList = []; - fnTypeSet.set(fnType.id, currentFnTypeList); - } - currentFnTypeList.push(fnType); - }; - for (const fnType of fnTypes) { - addFnTypeToFnTypeSet(fnType); - } - const doHandleQueryElemList = (currentFnTypeList, queryElemList) => { - if (queryElemList.length === 0) { return true; } - // Multiple items in one list might match multiple items in another. - // Since an item with fewer generics can match an item with more, we - // need to check all combinations for a potential match. - const queryElem = queryElemList.pop(); - const l = currentFnTypeList.length; - for (let i = 0; i < l; i += 1) { - const fnType = currentFnTypeList[i]; - if (!typePassesFilter(queryElem.typeFilter, fnType.ty)) { - continue; - } - const queryElemPathLength = queryElem.pathWithoutLast.length; - // If the query element is a path (it contains `::`), we need to check if this - // path is compatible with the target type. - if (queryElemPathLength > 0) { - const fnTypePath = fnType.path !== undefined && fnType.path !== null ? - fnType.path.split("::") : []; - // If the path provided in the query element is longer than this type, - // no need to check it since it won't match in any case. - if (queryElemPathLength > fnTypePath.length) { - continue; + return false; + }; + for (i = 0; i !== ql; ++i) { + const queryElem = queryElems[i]; + /** + * list of potential function types that go with the current query element. + * @type Array<integer> + */ + const matchCandidates = []; + let fnTypesScratch = null; + let mgensScratch = null; + // don't try anything before `i`, because they've already been + // paired off with the other query elements + for (j = i; j !== fl; ++j) { + const fnType = fnTypes[j]; + if (unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgens)) { + if (!fnTypesScratch) { + fnTypesScratch = fnTypes.slice(); } - let i = 0; - for (const path of fnTypePath) { - if (path === queryElem.pathWithoutLast[i]) { - i += 1; - if (i >= queryElemPathLength) { - break; - } + unifyFunctionTypes( + fnType.generics, + queryElem.generics, + whereClause, + mgens, + mgensScratch => { + matchCandidates.push({ + fnTypesScratch, + mgensScratch, + queryElemsOffset: i, + fnTypesOffset: j, + unbox: false, + }); + return false; // "reject" all candidates to gather all of them } + ); + } + if (unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens)) { + if (!fnTypesScratch) { + fnTypesScratch = fnTypes.slice(); } - if (i < queryElemPathLength) { - // If we didn't find all parts of the path of the query element inside - // the fn type, then it's not the right one. - continue; + if (!mgensScratch) { + mgensScratch = new Map(mgens); } + backtracking.push({ + fnTypesScratch, + mgensScratch, + queryElemsOffset: i, + fnTypesOffset: j, + unbox: true, + }); } - if (queryElem.generics.length === 0 || checkGenerics(fnType, queryElem)) { - currentFnTypeList.splice(i, 1); - const result = doHandleQueryElemList(currentFnTypeList, queryElemList); - if (result) { - return true; - } - currentFnTypeList.splice(i, 0, fnType); + } + if (matchCandidates.length === 0) { + if (backtrack()) { + continue; + } else { + return false; } } + // use the current candidate + const {fnTypesOffset: candidate, mgensScratch: mgensNew} = matchCandidates.pop(); + if (fnTypes[candidate].id < 0 && queryElems[i].id < 0) { + mgens.set(fnTypes[candidate].id, queryElems[i].id); + } + for (const [fid, qid] of mgensNew) { + mgens.set(fid, qid); + } + // `i` and `j` are paired off + // `queryElems[i]` is left in place + // `fnTypes[j]` is swapped with `fnTypes[i]` to pair them off + const tmp = fnTypes[candidate]; + fnTypes[candidate] = fnTypes[i]; + fnTypes[i] = tmp; + // write other candidates to backtracking queue + for (const otherCandidate of matchCandidates) { + backtracking.push(otherCandidate); + } + // If we're on the last item, check the solution with the callback + // backtrack if the callback says its unsuitable + while (i === (ql - 1) && solutionCb && !solutionCb(mgens)) { + if (!backtrack()) { + return false; + } + } + } + return true; + } + function unifyFunctionTypeIsMatchCandidate(fnType, queryElem, whereClause, mgens) { + // type filters look like `trait:Read` or `enum:Result` + if (!typePassesFilter(queryElem.typeFilter, fnType.ty)) { return false; - }; - const handleQueryElemList = (id, queryElemList) => { - if (!fnTypeSet.has(id)) { - if (id === typeNameIdOfArrayOrSlice) { - return handleQueryElemList(typeNameIdOfSlice, queryElemList) || - handleQueryElemList(typeNameIdOfArray, queryElemList); + } + // fnType.id < 0 means generic + // queryElem.id < 0 does too + // mgens[fnType.id] = queryElem.id + // or, if mgens[fnType.id] = 0, then we've matched this generic with a bare trait + // and should make that same decision everywhere it appears + if (fnType.id < 0 && queryElem.id < 0) { + if (mgens.has(fnType.id) && mgens.get(fnType.id) !== queryElem.id) { + return false; + } + for (const [fid, qid] of mgens.entries()) { + if (fnType.id !== fid && queryElem.id === qid) { + return false; } + if (fnType.id === fid && queryElem.id !== qid) { + return false; + } + } + } else if (fnType.id !== null) { + if (queryElem.id === typeNameIdOfArrayOrSlice && + (fnType.id === typeNameIdOfSlice || fnType.id === typeNameIdOfArray) + ) { + // [] matches primitive:array or primitive:slice + // if it matches, then we're fine, and this is an appropriate match candidate + } else if (fnType.id !== queryElem.id) { return false; } - const currentFnTypeList = fnTypeSet.get(id); - if (currentFnTypeList.length < queryElemList.length) { - // It's not possible for all the query elems to find a match. + // If the query elem has generics, and the function doesn't, + // it can't match. + if (fnType.generics.length === 0 && queryElem.generics.length !== 0) { return false; } - const result = doHandleQueryElemList(currentFnTypeList, queryElemList); - if (result) { - // Found a solution. - // Any items that weren't used for it can be unboxed, and might form - // part of the solution for another item. - for (const innerFnType of currentFnTypeList) { - addFnTypeToFnTypeSet(innerFnType); + // If the query element is a path (it contains `::`), we need to check if this + // path is compatible with the target type. + const queryElemPathLength = queryElem.pathWithoutLast.length; + if (queryElemPathLength > 0) { + const fnTypePath = fnType.path !== undefined && fnType.path !== null ? + fnType.path.split("::") : []; + // If the path provided in the query element is longer than this type, + // no need to check it since it won't match in any case. + if (queryElemPathLength > fnTypePath.length) { + return false; } - fnTypeSet.delete(id); - } - return result; - }; - let queryElemSetSize = -1; - while (queryElemSetSize !== queryElemSet.size) { - queryElemSetSize = queryElemSet.size; - for (const [id, queryElemList] of queryElemSet) { - if (handleQueryElemList(id, queryElemList)) { - queryElemSet.delete(id); + let i = 0; + for (const path of fnTypePath) { + if (path === queryElem.pathWithoutLast[i]) { + i += 1; + if (i >= queryElemPathLength) { + break; + } + } + } + if (i < queryElemPathLength) { + // If we didn't find all parts of the path of the query element inside + // the fn type, then it's not the right one. + return false; } } } - return queryElemSetSize === 0; + return true; + } + function unifyFunctionTypeIsUnboxCandidate(fnType, queryElem, whereClause, mgens) { + if (fnType.id < 0 && queryElem.id >= 0) { + if (!whereClause) { + return false; + } + // mgens[fnType.id] === 0 indicates that we committed to unboxing this generic + // mgens[fnType.id] === null indicates that we haven't decided yet + if (mgens.has(fnType.id) && mgens.get(fnType.id) !== 0) { + return false; + } + // This is only a potential unbox if the search query appears in the where clause + // for example, searching `Read -> usize` should find + // `fn read_all<R: Read>(R) -> Result<usize>` + // generic `R` is considered "unboxed" + return checkIfInList(whereClause[(-fnType.id) - 1], queryElem, whereClause); + } else if (fnType.generics && fnType.generics.length > 0) { + return checkIfInList(fnType.generics, queryElem, whereClause); + } + return false; } /** @@ -1541,13 +1624,14 @@ function initSearch(rawSearchIndex) { * generics (if any). * * @param {Array<FunctionType>} list - * @param {QueryElement} elem - The element from the parsed query. + * @param {QueryElement} elem - The element from the parsed query. + * @param {[FunctionType]} whereClause - Trait bounds for generic items. * * @return {boolean} - Returns true if found, false otherwise. */ - function checkIfInList(list, elem) { + function checkIfInList(list, elem, whereClause) { for (const entry of list) { - if (checkType(entry, elem)) { + if (checkType(entry, elem, whereClause)) { return true; } } @@ -1559,14 +1643,26 @@ function initSearch(rawSearchIndex) { * generics (if any). * * @param {Row} row - * @param {QueryElement} elem - The element from the parsed query. + * @param {QueryElement} elem - The element from the parsed query. + * @param {[FunctionType]} whereClause - Trait bounds for generic items. * * @return {boolean} - Returns true if the type matches, false otherwise. */ - function checkType(row, elem) { - if (row.id === -1) { + function checkType(row, elem, whereClause) { + if (row.id === null) { // This is a pure "generic" search, no need to run other checks. - return row.generics.length > 0 ? checkIfInList(row.generics, elem) : false; + return row.generics.length > 0 + ? checkIfInList(row.generics, elem, whereClause) + : false; + } + + if (row.id < 0 && elem.id >= 0) { + const gid = (-row.id) - 1; + return checkIfInList(whereClause[gid], elem, whereClause); + } + + if (row.id < 0 && elem.id < 0) { + return true; } const matchesExact = row.id === elem.id; @@ -1576,7 +1672,7 @@ function initSearch(rawSearchIndex) { if ((matchesExact || matchesArrayOrSlice) && typePassesFilter(elem.typeFilter, row.ty)) { if (elem.generics.length > 0) { - return checkGenerics(row, elem); + return checkGenerics(row, elem, whereClause, new Map()); } return true; } @@ -1584,7 +1680,7 @@ function initSearch(rawSearchIndex) { // If the current item does not match, try [unboxing] the generic. // [unboxing]: // https://ndmitchell.com/downloads/slides-hoogle_fast_type_searching-09_aug_2008.pdf - return checkIfInList(row.generics, elem); + return checkIfInList(row.generics, elem, whereClause); } function checkPath(contains, ty, maxEditDistance) { @@ -1785,13 +1881,15 @@ function initSearch(rawSearchIndex) { const fullId = row.id; const searchWord = searchWords[pos]; - const in_args = row.type && row.type.inputs && checkIfInList(row.type.inputs, elem); + const in_args = row.type && row.type.inputs + && checkIfInList(row.type.inputs, elem, row.type.where_clause); if (in_args) { // path_dist is 0 because no parent path information is currently stored // in the search index addIntoResults(results_in_args, fullId, pos, -1, 0, 0, maxEditDistance); } - const returned = row.type && row.type.output && checkIfInList(row.type.output, elem); + const returned = row.type && row.type.output + && checkIfInList(row.type.output, elem, row.type.where_clause); if (returned) { addIntoResults(results_returned, fullId, pos, -1, 0, 0, maxEditDistance); } @@ -1853,10 +1951,20 @@ function initSearch(rawSearchIndex) { } // If the result is too "bad", we return false and it ends this search. - if (!unifyFunctionTypes(row.type.inputs, parsedQuery.elems)) { - return; - } - if (!unifyFunctionTypes(row.type.output, parsedQuery.returned)) { + if (!unifyFunctionTypes( + row.type.inputs, + parsedQuery.elems, + row.type.where_clause, + null, + mgens => { + return unifyFunctionTypes( + row.type.output, + parsedQuery.returned, + row.type.where_clause, + mgens + ); + } + )) { return; } @@ -1876,6 +1984,11 @@ function initSearch(rawSearchIndex) { const maxEditDistance = Math.floor(queryLen / 3); /** + * @type {Map<string, integer>} + */ + const genericSymbols = new Map(); + + /** * Convert names to ids in parsed query elements. * This is not used for the "In Names" tab, but is used for the * "In Params", "In Returns", and "In Function Signature" tabs. @@ -1891,7 +2004,7 @@ function initSearch(rawSearchIndex) { if (typeNameIdMap.has(elem.pathLast)) { elem.id = typeNameIdMap.get(elem.pathLast); } else if (!parsedQuery.literalSearch) { - let match = -1; + let match = null; let matchDist = maxEditDistance + 1; let matchName = ""; for (const [name, id] of typeNameIdMap) { @@ -1905,11 +2018,52 @@ function initSearch(rawSearchIndex) { matchName = name; } } - if (match !== -1) { + if (match !== null) { parsedQuery.correction = matchName; } elem.id = match; } + if ((elem.id === null && parsedQuery.totalElems > 1 && elem.typeFilter === -1 + && elem.generics.length === 0) + || elem.typeFilter === TY_GENERIC) { + if (genericSymbols.has(elem.name)) { + elem.id = genericSymbols.get(elem.name); + } else { + elem.id = -(genericSymbols.size + 1); + genericSymbols.set(elem.name, elem.id); + } + if (elem.typeFilter === -1 && elem.name.length >= 3) { + // Silly heuristic to catch if the user probably meant + // to not write a generic parameter. We don't use it, + // just bring it up. + const maxPartDistance = Math.floor(elem.name.length / 3); + let matchDist = maxPartDistance + 1; + let matchName = ""; + for (const name of typeNameIdMap.keys()) { + const dist = editDistance(name, elem.name, maxPartDistance); + if (dist <= matchDist && dist <= maxPartDistance) { + if (dist === matchDist && matchName > name) { + continue; + } + matchDist = dist; + matchName = name; + } + } + if (matchName !== "") { + parsedQuery.proposeCorrectionFrom = elem.name; + parsedQuery.proposeCorrectionTo = matchName; + } + } + elem.typeFilter = TY_GENERIC; + } + if (elem.generics.length > 0 && elem.typeFilter === TY_GENERIC) { + // Rust does not have HKT + parsedQuery.error = [ + "Generic type parameter ", + elem.name, + " does not accept generic parameters", + ]; + } for (const elem2 of elem.generics) { convertNameToId(elem2); } @@ -1943,8 +2097,11 @@ function initSearch(rawSearchIndex) { elem = parsedQuery.returned[0]; for (i = 0, nSearchWords = searchWords.length; i < nSearchWords; ++i) { row = searchIndex[i]; - in_returned = row.type && - unifyFunctionTypes(row.type.output, parsedQuery.returned); + in_returned = row.type && unifyFunctionTypes( + row.type.output, + parsedQuery.returned, + row.type.where_clause + ); if (in_returned) { addIntoResults( results_others, @@ -2295,6 +2452,13 @@ ${item.displayPath}<span class="${type}">${name}</span>\ "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"; @@ -2396,37 +2560,54 @@ ${item.displayPath}<span class="${type}">${name}</span>\ * @return {Array<FunctionSearchType>} */ function buildItemSearchTypeAll(types, lowercasePaths) { + return types.map(type => buildItemSearchType(type, lowercasePaths)); + } + + /** + * Converts a single type. + * + * @param {RawFunctionType} type + */ + function buildItemSearchType(type, lowercasePaths) { const PATH_INDEX_DATA = 0; const GENERICS_DATA = 1; - return types.map(type => { - let pathIndex, generics; - if (typeof type === "number") { - pathIndex = type; - generics = []; - } else { - pathIndex = type[PATH_INDEX_DATA]; - generics = buildItemSearchTypeAll( - type[GENERICS_DATA], - lowercasePaths - ); - } + let pathIndex, generics; + if (typeof type === "number") { + pathIndex = type; + generics = []; + } else { + pathIndex = type[PATH_INDEX_DATA]; + generics = buildItemSearchTypeAll( + type[GENERICS_DATA], + lowercasePaths + ); + } + if (pathIndex < 0) { + // types less than 0 are generic parameters + // the actual names of generic parameters aren't stored, since they aren't API + return { + id: pathIndex, + ty: TY_GENERIC, + path: null, + generics, + }; + } + if (pathIndex === 0) { // `0` is used as a sentinel because it's fewer bytes than `null` - if (pathIndex === 0) { - return { - id: -1, - ty: null, - path: null, - generics: generics, - }; - } - const item = lowercasePaths[pathIndex - 1]; return { - id: buildTypeMapIndex(item.name), - ty: item.ty, - path: item.path, - generics: generics, + id: null, + ty: null, + path: null, + generics, }; - }); + } + const item = lowercasePaths[pathIndex - 1]; + return { + id: buildTypeMapIndex(item.name), + ty: item.ty, + path: item.path, + generics, + }; } /** @@ -2454,23 +2635,7 @@ ${item.displayPath}<span class="${type}">${name}</span>\ } let inputs, output; if (typeof functionSearchType[INPUTS_DATA] === "number") { - const pathIndex = functionSearchType[INPUTS_DATA]; - if (pathIndex === 0) { - inputs = [{ - id: -1, - ty: null, - path: null, - generics: [], - }]; - } else { - const item = lowercasePaths[pathIndex - 1]; - inputs = [{ - id: buildTypeMapIndex(item.name), - ty: item.ty, - path: item.path, - generics: [], - }]; - } + inputs = [buildItemSearchType(functionSearchType[INPUTS_DATA], lowercasePaths)]; } else { inputs = buildItemSearchTypeAll( functionSearchType[INPUTS_DATA], @@ -2479,23 +2644,7 @@ ${item.displayPath}<span class="${type}">${name}</span>\ } if (functionSearchType.length > 1) { if (typeof functionSearchType[OUTPUT_DATA] === "number") { - const pathIndex = functionSearchType[OUTPUT_DATA]; - if (pathIndex === 0) { - output = [{ - id: -1, - ty: null, - path: null, - generics: [], - }]; - } else { - const item = lowercasePaths[pathIndex - 1]; - output = [{ - id: buildTypeMapIndex(item.name), - ty: item.ty, - path: item.path, - generics: [], - }]; - } + output = [buildItemSearchType(functionSearchType[OUTPUT_DATA], lowercasePaths)]; } else { output = buildItemSearchTypeAll( functionSearchType[OUTPUT_DATA], @@ -2505,8 +2654,15 @@ ${item.displayPath}<span class="${type}">${name}</span>\ } 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, + inputs, output, where_clause, }; } diff --git a/src/tools/rustdoc-js/tester.js b/src/tools/rustdoc-js/tester.js index 416517d15f5..c7e6dd3615e 100644 --- a/src/tools/rustdoc-js/tester.js +++ b/src/tools/rustdoc-js/tester.js @@ -23,7 +23,9 @@ function contentToDiffLine(key, value) { } function shouldIgnoreField(fieldName) { - return fieldName === "query" || fieldName === "correction"; + return fieldName === "query" || fieldName === "correction" || + fieldName === "proposeCorrectionFrom" || + fieldName === "proposeCorrectionTo"; } // This function is only called when no matching result was found and therefore will only display diff --git a/tests/rustdoc-gui/search-corrections.goml b/tests/rustdoc-gui/search-corrections.goml index 5d1b83b35c5..aeb3c9b31a3 100644 --- a/tests/rustdoc-gui/search-corrections.goml +++ b/tests/rustdoc-gui/search-corrections.goml @@ -54,3 +54,53 @@ assert-text: ( ".search-corrections", "Type \"notablestructwithlongnamr\" not found. Showing results for closest type name \"notablestructwithlongname\" instead." ) + +// Now, generic correction +go-to: "file://" + |DOC_PATH| + "/test_docs/index.html" +// Intentionally wrong spelling of "NotableStructWithLongName" +write: (".search-input", "NotableStructWithLongNamr, NotableStructWithLongNamr") +// To be SURE that the search will be run. +press-key: 'Enter' +// Waiting for the search results to appear... +wait-for: "#search-tabs" + +assert-css: (".search-corrections", { + "display": "block" +}) +assert-text: ( + ".search-corrections", + "Type \"notablestructwithlongnamr\" not found and used as generic parameter. Consider searching for \"notablestructwithlongname\" instead." +) + +// Now, generic correction plus error +go-to: "file://" + |DOC_PATH| + "/test_docs/index.html" +// Intentionally wrong spelling of "NotableStructWithLongName" +write: (".search-input", "Foo<NotableStructWithLongNamr>,y") +// To be SURE that the search will be run. +press-key: 'Enter' +// Waiting for the search results to appear... +wait-for: "#search-tabs" + +assert-css: (".search-corrections", { + "display": "block" +}) +assert-text: ( + ".search-corrections", + "Type \"notablestructwithlongnamr\" not found and used as generic parameter. Consider searching for \"notablestructwithlongname\" instead." +) + +go-to: "file://" + |DOC_PATH| + "/test_docs/index.html" +// Intentionally wrong spelling of "NotableStructWithLongName" +write: (".search-input", "generic:NotableStructWithLongNamr<x>,y") +// To be SURE that the search will be run. +press-key: 'Enter' +// Waiting for the search results to appear... +wait-for: "#search-tabs" + +assert-css: (".error", { + "display": "block" +}) +assert-text: ( + ".error", + "Query parser error: \"Generic type parameter notablestructwithlongnamr does not accept generic parameters\"." +) diff --git a/tests/rustdoc-js-std/option-type-signatures.js b/tests/rustdoc-js-std/option-type-signatures.js index 25997850661..e154fa707ab 100644 --- a/tests/rustdoc-js-std/option-type-signatures.js +++ b/tests/rustdoc-js-std/option-type-signatures.js @@ -1,3 +1,7 @@ +// ignore-order + +const FILTER_CRATE = "std"; + const EXPECTED = [ { 'query': 'option, fnonce -> option', @@ -19,4 +23,62 @@ const EXPECTED = [ { 'path': 'std::option::Option', 'name': 'as_mut_slice' }, ], }, + { + 'query': 'option<t>, option<t> -> option<t>', + 'others': [ + { 'path': 'std::option::Option', 'name': 'or' }, + { 'path': 'std::option::Option', 'name': 'xor' }, + ], + }, + { + 'query': 'option<t>, option<u> -> option<u>', + 'others': [ + { 'path': 'std::option::Option', 'name': 'and' }, + { 'path': 'std::option::Option', 'name': 'zip' }, + ], + }, + { + 'query': 'option<t>, option<u> -> option<t>', + 'others': [ + { 'path': 'std::option::Option', 'name': 'and' }, + { 'path': 'std::option::Option', 'name': 'zip' }, + ], + }, + { + 'query': 'option<t>, option<u> -> option<t, u>', + 'others': [ + { 'path': 'std::option::Option', 'name': 'zip' }, + ], + }, + { + 'query': 'option<t>, e -> result<t, e>', + 'others': [ + { 'path': 'std::option::Option', 'name': 'ok_or' }, + { 'path': 'std::result::Result', 'name': 'transpose' }, + ], + }, + { + 'query': 'result<option<t>, e> -> option<result<t, e>>', + 'others': [ + { 'path': 'std::result::Result', 'name': 'transpose' }, + ], + }, + { + 'query': 'option<t>, option<t> -> bool', + 'others': [ + { 'path': 'std::option::Option', 'name': 'eq' }, + ], + }, + { + 'query': 'option<option<t>> -> option<t>', + 'others': [ + { 'path': 'std::option::Option', 'name': 'flatten' }, + ], + }, + { + 'query': 'option<t>', + 'returned': [ + { 'path': 'std::result::Result', 'name': 'ok' }, + ], + }, ]; diff --git a/tests/rustdoc-js-std/vec-type-signatures.js b/tests/rustdoc-js-std/vec-type-signatures.js new file mode 100644 index 00000000000..18cf9d6efd0 --- /dev/null +++ b/tests/rustdoc-js-std/vec-type-signatures.js @@ -0,0 +1,22 @@ +// ignore-order + +const FILTER_CRATE = "std"; + +const EXPECTED = [ + { + 'query': 'vec::intoiter<T> -> [T]', + 'others': [ + { 'path': 'std::vec::IntoIter', 'name': 'as_slice' }, + { 'path': 'std::vec::IntoIter', 'name': 'as_mut_slice' }, + { 'path': 'std::vec::IntoIter', 'name': 'next_chunk' }, + ], + }, + { + 'query': 'vec::intoiter<T> -> []', + 'others': [ + { 'path': 'std::vec::IntoIter', 'name': 'as_slice' }, + { 'path': 'std::vec::IntoIter', 'name': 'as_mut_slice' }, + { 'path': 'std::vec::IntoIter', 'name': 'next_chunk' }, + ], + }, +]; diff --git a/tests/rustdoc-js/generics-match-ambiguity.js b/tests/rustdoc-js/generics-match-ambiguity.js index a9932a16ca3..edce4268c5a 100644 --- a/tests/rustdoc-js/generics-match-ambiguity.js +++ b/tests/rustdoc-js/generics-match-ambiguity.js @@ -79,6 +79,7 @@ const EXPECTED = [ { 'path': 'generics_match_ambiguity', 'name': 'baac' }, { 'path': 'generics_match_ambiguity', 'name': 'baaf' }, { 'path': 'generics_match_ambiguity', 'name': 'baag' }, + { 'path': 'generics_match_ambiguity', 'name': 'baah' }, ], }, { diff --git a/tests/rustdoc-js/generics-trait.js b/tests/rustdoc-js/generics-trait.js index 4ccfb8f4e4d..a71393b5e05 100644 --- a/tests/rustdoc-js/generics-trait.js +++ b/tests/rustdoc-js/generics-trait.js @@ -12,12 +12,16 @@ const EXPECTED = [ ], }, { - 'query': 'Result<SomeTraiz>', - 'correction': null, + 'query': 'Resulx<SomeTrait>', 'in_args': [], 'returned': [], }, { + 'query': 'Result<SomeTraiz>', + 'proposeCorrectionFrom': 'SomeTraiz', + 'proposeCorrectionTo': 'SomeTrait', + }, + { 'query': 'OtherThingxxxxxxxx', 'correction': null, 'in_args': [ diff --git a/tests/rustdoc-js/generics-unbox.js b/tests/rustdoc-js/generics-unbox.js new file mode 100644 index 00000000000..9cdfc7ac8b6 --- /dev/null +++ b/tests/rustdoc-js/generics-unbox.js @@ -0,0 +1,38 @@ +// exact-check + +const EXPECTED = [ + { + 'query': 'Inside<T> -> Out1<T>', + 'others': [ + { 'path': 'generics_unbox', 'name': 'alpha' }, + ], + }, + { + 'query': 'Inside<T> -> Out3<T>', + 'others': [ + { 'path': 'generics_unbox', 'name': 'beta' }, + { 'path': 'generics_unbox', 'name': 'gamma' }, + ], + }, + { + 'query': 'Inside<T> -> Out4<T>', + 'others': [ + { 'path': 'generics_unbox', 'name': 'beta' }, + { 'path': 'generics_unbox', 'name': 'gamma' }, + ], + }, + { + 'query': 'Inside<T> -> Out3<U, T>', + 'others': [ + { 'path': 'generics_unbox', 'name': 'beta' }, + { 'path': 'generics_unbox', 'name': 'gamma' }, + ], + }, + { + 'query': 'Inside<T> -> Out4<U, T>', + 'others': [ + { 'path': 'generics_unbox', 'name': 'beta' }, + { 'path': 'generics_unbox', 'name': 'gamma' }, + ], + }, +]; diff --git a/tests/rustdoc-js/generics-unbox.rs b/tests/rustdoc-js/generics-unbox.rs new file mode 100644 index 00000000000..bef34f891e9 --- /dev/null +++ b/tests/rustdoc-js/generics-unbox.rs @@ -0,0 +1,36 @@ +pub struct Out<A, B = ()> { + a: A, + b: B, +} + +pub struct Out1<A, const N: usize> { + a: [A; N], +} + +pub struct Out2<A, const N: usize> { + a: [A; N], +} + +pub struct Out3<A, B> { + a: A, + b: B, +} + +pub struct Out4<A, B> { + a: A, + b: B, +} + +pub struct Inside<T>(T); + +pub fn alpha<const N: usize, T>(_: Inside<T>) -> Out<Out1<T, N>, Out2<T, N>> { + loop {} +} + +pub fn beta<T, U>(_: Inside<T>) -> Out<Out3<T, U>, Out4<U, T>> { + loop {} +} + +pub fn gamma<T, U>(_: Inside<T>) -> Out<Out3<U, T>, Out4<T, U>> { + loop {} +} diff --git a/tests/rustdoc-js/type-parameters.js b/tests/rustdoc-js/type-parameters.js new file mode 100644 index 00000000000..e695f189bb6 --- /dev/null +++ b/tests/rustdoc-js/type-parameters.js @@ -0,0 +1,87 @@ +// exact-check +// ignore-order + +const EXPECTED = [ + { + query: '-> trait:Some', + others: [ + { path: 'foo', name: 'alef' }, + { path: 'foo', name: 'alpha' }, + ], + }, + { + query: '-> generic:T', + others: [ + { path: 'foo', name: 'bet' }, + { path: 'foo', name: 'alef' }, + { path: 'foo', name: 'beta' }, + ], + }, + { + query: 'A -> B', + others: [ + { path: 'foo', name: 'bet' }, + ], + }, + { + query: 'A -> A', + others: [ + { path: 'foo', name: 'beta' }, + ], + }, + { + query: 'A, A', + others: [ + { path: 'foo', name: 'alternate' }, + ], + }, + { + query: 'A, B', + others: [ + { path: 'foo', name: 'other' }, + ], + }, + { + query: 'Other, Other', + others: [ + { path: 'foo', name: 'other' }, + { path: 'foo', name: 'alternate' }, + ], + }, + { + query: 'generic:T', + in_args: [ + { path: 'foo', name: 'bet' }, + { path: 'foo', name: 'beta' }, + { path: 'foo', name: 'other' }, + { path: 'foo', name: 'alternate' }, + ], + }, + { + query: 'generic:Other', + in_args: [ + { path: 'foo', name: 'bet' }, + { path: 'foo', name: 'beta' }, + { path: 'foo', name: 'other' }, + { path: 'foo', name: 'alternate' }, + ], + }, + { + query: 'trait:Other', + in_args: [ + { path: 'foo', name: 'other' }, + { path: 'foo', name: 'alternate' }, + ], + }, + { + query: 'Other', + in_args: [ + { path: 'foo', name: 'other' }, + { path: 'foo', name: 'alternate' }, + ], + }, + { + query: 'trait:T', + in_args: [], + }, +]; diff --git a/tests/rustdoc-js/type-parameters.rs b/tests/rustdoc-js/type-parameters.rs new file mode 100644 index 00000000000..cda5e26171f --- /dev/null +++ b/tests/rustdoc-js/type-parameters.rs @@ -0,0 +1,15 @@ +#![crate_name="foo"] + +pub trait Some {} +impl Some for () {} +pub trait Other {} +impl Other for () {} + +pub fn alef<T: Some>() -> T { loop {} } +pub fn alpha() -> impl Some { } + +pub fn bet<T, U>(t: T) -> U { loop {} } +pub fn beta<T>(t: T) -> T {} + +pub fn other<T: Other, U: Other>(t: T, u: U) { loop {} } +pub fn alternate<T: Other>(t: T, u: T) { loop {} } |