1 //! Definitions of runtime structures and metadata which are serialized into ELF 2 //! with `bincode` as part of a module's compilation process. 3 4 use crate::prelude::*; 5 use crate::{FilePos, FuncIndex, FuncKey, FuncKeyIndex, FuncKeyKind, FuncKeyNamespace, Module}; 6 use core::ops::Range; 7 use core::{fmt, u32}; 8 use core::{iter, str}; 9 use cranelift_entity::{EntityRef, PrimaryMap}; 10 use serde_derive::{Deserialize, Serialize}; 11 12 /// Description of where a function is located in the text section of a 13 /// compiled image. 14 #[derive(Copy, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)] 15 pub struct FunctionLoc { 16 /// The byte offset from the start of the text section where this 17 /// function starts. 18 pub start: u32, 19 /// The byte length of this function's function body. 20 pub length: u32, 21 } 22 23 impl FunctionLoc { 24 /// Is this an empty function location? 25 #[inline] 26 pub fn is_empty(&self) -> bool { 27 self.length == 0 28 } 29 } 30 31 /// A builder for a `CompiledFunctionsTable`. 32 pub struct CompiledFunctionsTableBuilder { 33 inner: CompiledFunctionsTable, 34 } 35 36 impl CompiledFunctionsTableBuilder { 37 /// Create a new builder. 38 pub fn new() -> Self { 39 Self { 40 inner: CompiledFunctionsTable { 41 namespaces: PrimaryMap::new(), 42 func_loc_starts: PrimaryMap::new(), 43 sparse_starts: PrimaryMap::new(), 44 src_loc_starts: PrimaryMap::new(), 45 sparse_indices: PrimaryMap::new(), 46 func_locs: PrimaryMap::new(), 47 src_locs: PrimaryMap::new(), 48 }, 49 } 50 } 51 52 fn last_namespace(&self) -> Option<FuncKeyNamespace> { 53 let (_, &ns) = self.inner.namespaces.last()?; 54 Some(ns) 55 } 56 57 fn last_key_index(&self) -> Option<FuncKeyIndex> { 58 let (ns_idx, ns) = self.inner.namespaces.last()?; 59 let start = self.inner.func_loc_starts[ns_idx]; 60 if CompiledFunctionsTable::is_dense(ns.kind()) { 61 let len = self.inner.func_locs.len(); 62 let len = u32::try_from(len).unwrap(); 63 let key_index = len - start.as_u32(); 64 let key_index = FuncKeyIndex::from_raw(key_index); 65 Some(key_index) 66 } else { 67 let sparse_start = self.inner.sparse_starts[ns_idx]; 68 if self.inner.sparse_indices.len() > sparse_start.index() { 69 let (_, &key_index) = self.inner.sparse_indices.last().unwrap(); 70 Some(key_index) 71 } else { 72 None 73 } 74 } 75 } 76 77 fn last_func_loc(&self) -> Option<FunctionLoc> { 78 let (_, &loc) = self.inner.func_locs.last()?; 79 Some(loc) 80 } 81 82 /// Push a new entry into this builder. 83 /// 84 /// Panics if the key or function location is out of order. 85 pub fn push_func( 86 &mut self, 87 key: FuncKey, 88 func_loc: FunctionLoc, 89 src_loc: FilePos, 90 ) -> &mut Self { 91 let (key_ns, key_index) = key.into_parts(); 92 93 assert!( 94 self.last_namespace().is_none_or(|ns| ns <= key_ns), 95 "`FuncKey`s pushed out of order" 96 ); 97 assert!( 98 self.last_key_index().is_none_or( 99 |i| i <= key_index || self.last_namespace().is_some_and(|ns| ns != key_ns) 100 ), 101 "`FuncKey`s pushed out of order" 102 ); 103 assert!( 104 self.last_func_loc() 105 .is_none_or(|l| l.start + l.length <= func_loc.start), 106 "`FunctionLoc`s pushed out of order" 107 ); 108 109 // Make sure that there is a `kind` entry for this key's kind. 110 let kind_start_index = self 111 .inner 112 .namespaces 113 .last() 114 .and_then(|(ns_idx, ns)| { 115 if *ns == key_ns { 116 Some(self.inner.func_loc_starts[ns_idx]) 117 } else { 118 None 119 } 120 }) 121 .unwrap_or_else(|| { 122 let start = self.inner.func_locs.next_key(); 123 let ns_idx = self.inner.namespaces.push(key_ns); 124 let ns_idx2 = self.inner.func_loc_starts.push(start); 125 let ns_idx3 = self 126 .inner 127 .sparse_starts 128 .push(self.inner.sparse_indices.next_key()); 129 let ns_idx4 = self 130 .inner 131 .src_loc_starts 132 .push(self.inner.src_locs.next_key()); 133 debug_assert_eq!(ns_idx, ns_idx2); 134 debug_assert_eq!(ns_idx, ns_idx3); 135 debug_assert_eq!(ns_idx, ns_idx4); 136 start 137 }); 138 139 if CompiledFunctionsTable::is_dense(key.kind()) { 140 // Figure out the index within `func_locs` for this key's entry. 141 let index = kind_start_index.as_u32() + key_index.into_raw(); 142 let index = FuncLocIndex::from_u32(index); 143 debug_assert!(self.inner.func_locs.get(index).is_none()); 144 145 // Fill in null entries for any key indices that have been omitted. 146 // 147 // Note that we need a null `FunctionLoc`, but we also need 148 // `func_locs` to be sorted so that we support reverse 149 // lookups. Therefore, we take care to create an empty function 150 // location that starts at the text offset that the previous one (if 151 // any) ends at, and use that as our null entry. 152 let null_func_loc = FunctionLoc { 153 start: self 154 .last_func_loc() 155 .map(|l| l.start + l.length) 156 .unwrap_or_default(), 157 length: 0, 158 }; 159 let gap = index.index() - self.inner.func_locs.len(); 160 self.inner 161 .func_locs 162 .extend(iter::repeat(null_func_loc).take(gap)); 163 debug_assert_eq!(index, self.inner.func_locs.next_key()); 164 165 if CompiledFunctionsTable::has_src_locs(key_ns.kind()) { 166 self.inner 167 .src_locs 168 .extend(iter::repeat(FilePos::none()).take(gap)); 169 } 170 } else { 171 debug_assert!( 172 src_loc.is_none(), 173 "sparse keys do not have source locations" 174 ); 175 self.inner.sparse_indices.push(key_index); 176 } 177 178 // And finally, we push this entry. 179 self.inner.func_locs.push(func_loc); 180 if CompiledFunctionsTable::has_src_locs(key_ns.kind()) { 181 self.inner.src_locs.push(src_loc); 182 } else { 183 debug_assert!(src_loc.is_none()); 184 } 185 186 self 187 } 188 189 /// Finish construction of the `CompiledFunctionsTable`. 190 pub fn finish(self) -> CompiledFunctionsTable { 191 self.inner 192 } 193 } 194 195 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)] 196 struct NamespaceIndex(u32); 197 cranelift_entity::entity_impl!(NamespaceIndex); 198 199 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)] 200 struct FuncLocIndex(u32); 201 cranelift_entity::entity_impl!(FuncLocIndex); 202 203 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)] 204 struct SparseIndex(u32); 205 cranelift_entity::entity_impl!(SparseIndex); 206 207 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)] 208 struct SrcLocIndex(u32); 209 cranelift_entity::entity_impl!(SrcLocIndex); 210 211 /// A table describing the set of functions compiled into an artifact, their 212 /// locations within the text section, and etc... 213 /// 214 /// Logically, this type is a map from a `FuncKey` to the associated function's 215 /// 216 /// * location within the associated text section, and 217 /// * optional source location. 218 /// 219 /// How this map is *actually* implemented is with a series of lookup and binary 220 /// search tables, split out in a data-oriented, struct-of-arrays style. We 221 /// organize the data in this way is service of three goals: 222 /// 223 /// 1. Provide fast look ups: We need to look up the metadata for a function by 224 /// its key at runtime. During instantiation, for example, we need to create 225 /// `VMFuncRef`s for escaping functions and this requires looking up the 226 /// locations of those Wasm functions and their associated array-to-Wasm 227 /// trampolines. 228 /// 229 /// 2. Keep memory overheads low and code size small: This type is serialized 230 /// into all of our ELF artifacts and deserialized into all `Module`s and 231 /// `Component`s at runtime. 232 /// 233 /// 3. Be generic over any kind of function (whether defined Wasm function, 234 /// trampoline, or etc...) that we compile: Adding a new kind of trampoline, 235 /// for example, should not require updating this structure to add a new 236 /// table of the function locations for just trampolines of that new kind. We 237 /// should be able to store and query all kinds of functions uniformly. 238 // 239 // TODO: This structure could be directly encoded as raw ELF sections, instead 240 // of a `struct` containing a bunch of `PrimaryMap`s, which would allow us to 241 // avoid the serialize/deserialize runtime costs. 242 #[derive(Debug, Serialize, Deserialize)] 243 pub struct CompiledFunctionsTable { 244 /// A binary-search index for this table, mapping raw `FuncKeyNamespace`s to 245 /// their associated `NamespaceIndex`. That `NamespaceIndex` can then be 246 /// used to find the range of other entity indices that are specific to that 247 /// namespace. 248 namespaces: PrimaryMap<NamespaceIndex, FuncKeyNamespace>, 249 250 /// `self.func_loc_starts[i]..self.func_loc_starts[i+1]` describes the range 251 /// within `self.func_locs` whose entries are associated with the namespace 252 /// `self.index[i]`. 253 /// 254 /// When `self.func_loc_starts[i+1]` is out of bounds, then the range is to 255 /// the end of `self.func_locs`. 256 func_loc_starts: PrimaryMap<NamespaceIndex, FuncLocIndex>, 257 258 /// `self.sparse_starts[i]..self.sparse_starts[i+1]` describes the range 259 /// within `self.sparse_indices` whose entries are associated with the 260 /// namespace `self.index[i]`. 261 /// 262 /// When `self.sparse_starts[i+1]` is out of bounds, then the range is to 263 /// the end of `self.sparse_indices`. 264 /// 265 /// Entries are only valid for sparse, non-dense namespaces. 266 sparse_starts: PrimaryMap<NamespaceIndex, SparseIndex>, 267 268 /// `self.src_loc_starts[i]..self.src_loc_starts[i+1]` describes the range 269 /// within `self.src_loc_indices` whose entries are associated with the 270 /// namespace `self.index[i]`. 271 /// 272 /// When `self.src_loc_starts[i+1]` is out of bounds, then the range is to 273 /// the end of `self.src_locs`. 274 /// 275 /// Entries are only valid for namespaces whose functions have source 276 /// locations. 277 src_loc_starts: PrimaryMap<NamespaceIndex, SrcLocIndex>, 278 279 /// `self.sparse_indices[i]` contains the index part of 280 /// `FuncKey::from_parts(ns, index)` where `ns` is determined by 281 /// `self.sparse_starts` and is a sparse, non-dense key kind. (Note that for 282 /// dense keys, this information is implicitly encoded in their offset from 283 /// the namespace's start index.) 284 /// 285 /// This is sorted to allow for binary searches. 286 sparse_indices: PrimaryMap<SparseIndex, FuncKeyIndex>, 287 288 /// `self.func_locs[i]` contains the location within the text section of 289 /// `FuncKey::from_parts(self.namespaces[ns], i - start)`'s function, where 290 /// `ns` and `start` are determined by `self.func_loc_starts`. 291 /// 292 /// Values are sorted by function location to support reverse queries from 293 /// function location back to `FuncKey`. 294 /// 295 /// The absence of a function location (for gaps in dense namespaces) is 296 /// represented with `FunctionLoc::none()`. 297 func_locs: PrimaryMap<FuncLocIndex, FunctionLoc>, 298 299 /// `self.src_locs[i]` contains the initial source location of 300 /// `FuncKey::from_parts(self.namespaces[ns], i - start)`'s function, where 301 /// `ns` and `start` are determined by `self.src_loc_starts`. 302 /// 303 /// The absence of a source location is represented by `FilePos::none()`. 304 src_locs: PrimaryMap<SrcLocIndex, FilePos>, 305 } 306 307 impl CompiledFunctionsTable { 308 #[inline] 309 fn namespace_index(&self, namespace: FuncKeyNamespace) -> Option<NamespaceIndex> { 310 const LINEAR_SEARCH_LIMIT: usize = 32; 311 if self.namespaces.len() <= LINEAR_SEARCH_LIMIT { 312 self.namespaces 313 .iter() 314 .find_map(|(idx, ns)| if *ns == namespace { Some(idx) } else { None }) 315 } else { 316 self.namespaces 317 .binary_search_values_by_key(&namespace, |ns| *ns) 318 .ok() 319 } 320 } 321 322 #[inline] 323 fn func_loc_range(&self, ns_idx: NamespaceIndex) -> Range<FuncLocIndex> { 324 let start = self.func_loc_starts[ns_idx]; 325 let next_ns_idx = NamespaceIndex::from_u32(ns_idx.as_u32() + 1); 326 let end = self 327 .func_loc_starts 328 .get(next_ns_idx) 329 .copied() 330 .unwrap_or_else(|| self.func_locs.next_key()); 331 start..end 332 } 333 334 fn sparse_range(&self, ns_idx: NamespaceIndex) -> Range<SparseIndex> { 335 debug_assert!(!Self::is_dense(self.namespaces[ns_idx].kind())); 336 let start = self.sparse_starts[ns_idx]; 337 let next_ns_idx = NamespaceIndex::from_u32(ns_idx.as_u32() + 1); 338 let end = self 339 .sparse_starts 340 .get(next_ns_idx) 341 .copied() 342 .unwrap_or_else(|| self.sparse_indices.next_key()); 343 start..end 344 } 345 346 fn src_loc_range(&self, ns_idx: NamespaceIndex) -> Range<SrcLocIndex> { 347 debug_assert!(Self::has_src_locs(self.namespaces[ns_idx].kind())); 348 let start = self.src_loc_starts[ns_idx]; 349 let next_ns_idx = NamespaceIndex::from_u32(ns_idx.as_u32() + 1); 350 let end = self 351 .src_loc_starts 352 .get(next_ns_idx) 353 .copied() 354 .unwrap_or_else(|| self.src_locs.next_key()); 355 start..end 356 } 357 358 /// Get the index within `self.{func_locs,src_locs}` that is associated with 359 /// the given `key`, if any. 360 #[inline] 361 fn func_loc_index(&self, key: FuncKey) -> Option<FuncLocIndex> { 362 let (key_ns, key_index) = key.into_parts(); 363 let ns_idx = self.namespace_index(key_ns)?; 364 let Range { start, end } = self.func_loc_range(ns_idx); 365 366 let index = if Self::is_dense(key.kind()) { 367 let index = start.as_u32().checked_add(key_index.into_raw())?; 368 FuncLocIndex::from_u32(index) 369 } else { 370 let sparse_range = self.sparse_range(ns_idx); 371 let sparse_subslice = self.sparse_indices.get_range(sparse_range).unwrap(); 372 match sparse_subslice.binary_search(&key_index) { 373 Ok(i) => FuncLocIndex::new(start.index() + i), 374 Err(_) => return None, 375 } 376 }; 377 378 if index < end { Some(index) } else { None } 379 } 380 381 /// Get the location of the function associated with the given `key` inside 382 /// the text section, if any. 383 #[inline] 384 pub fn func_loc(&self, key: FuncKey) -> Option<&FunctionLoc> { 385 let index = self.func_loc_index(key)?; 386 let loc = &self.func_locs[index]; 387 if loc.is_empty() { None } else { Some(loc) } 388 } 389 390 fn src_loc_index(&self, key: FuncKey) -> Option<SrcLocIndex> { 391 let (key_ns, key_index) = key.into_parts(); 392 if !Self::has_src_locs(key_ns.kind()) { 393 return None; 394 } 395 396 let ns_idx = self.namespace_index(key_ns)?; 397 let Range { start, end } = self.src_loc_range(ns_idx); 398 399 debug_assert!(Self::is_dense(key_ns.kind())); 400 let index = start.as_u32().checked_add(key_index.into_raw())?; 401 let index = SrcLocIndex::from_u32(index); 402 if index >= end { 403 return None; 404 } 405 406 Some(index) 407 } 408 409 /// Get the initial source location of the function associated with the 410 /// given `key`, if any. 411 pub fn src_loc(&self, key: FuncKey) -> Option<FilePos> { 412 let index = self.src_loc_index(key)?; 413 let loc = self.src_locs[index]; 414 if loc.is_none() { None } else { Some(loc) } 415 } 416 417 /// Given an offset into the text section, get the key for its associated 418 /// function and its offset within that function. 419 pub fn func_by_text_offset(&self, text_offset: u32) -> Option<FuncKey> { 420 let index = match self.func_locs.as_values_slice().binary_search_by(|loc| { 421 if loc.is_empty() { 422 loc.start 423 .cmp(&text_offset) 424 .then_with(|| core::cmp::Ordering::Less) 425 } else { 426 if loc.start > text_offset { 427 core::cmp::Ordering::Greater 428 } else if loc.start + loc.length <= text_offset { 429 core::cmp::Ordering::Less 430 } else { 431 debug_assert!(loc.start <= text_offset); 432 debug_assert!(text_offset < loc.start + loc.length); 433 core::cmp::Ordering::Equal 434 } 435 } 436 }) { 437 // Exact match, the offset is at the end of this function. 438 Ok(k) => k, 439 // Not an exact match: `k` is where the offset would be 440 // "inserted". Since we key based on the end, function `k` might 441 // contain the offset, so we'll validate on the range check 442 // below. 443 Err(k) => k, 444 }; 445 let index = FuncLocIndex::new(index); 446 447 // Make sure that the text offset is actually within this function. 448 // Non-exact binary search results can either be because we have a text 449 // offset within a function but not exactly at its inclusive end, or 450 // because the text offset is not within any of our functions. We filter 451 // that latter case out with this check. 452 let loc = self.func_locs.get(index)?; 453 let start = loc.start; 454 let end = start + loc.length; 455 if text_offset < start || end < text_offset { 456 return None; 457 } 458 459 let ns_idx = match self 460 .func_loc_starts 461 .binary_search_values_by_key(&index, |s| *s) 462 { 463 // Exact match: `i` is the entry's index. 464 Ok(i) => i, 465 // Not an exact match: the index, if it were the start of a 466 // namespace's range, would be at `i`. Therefore, our namespace 467 // entry is actually at index `i - 1`. 468 Err(i) => { 469 let i = i.as_u32(); 470 assert_ne!(i, 0); 471 NamespaceIndex::from_u32(i - 1) 472 } 473 }; 474 let key_ns = self.namespaces[ns_idx]; 475 let start = self.func_loc_starts[ns_idx]; 476 477 let key_index = if Self::is_dense(key_ns.kind()) { 478 let key_index = index.as_u32() - start.as_u32(); 479 FuncKeyIndex::from_raw(key_index) 480 } else { 481 let sparse_offset = index.as_u32() - start.as_u32(); 482 let sparse_start = self.sparse_starts[ns_idx]; 483 let sparse_index = SparseIndex::from_u32(sparse_start.as_u32() + sparse_offset); 484 debug_assert!( 485 { 486 let range = self.sparse_range(ns_idx); 487 range.start <= sparse_index && sparse_index < range.end 488 }, 489 "{sparse_index:?} is not within {:?}", 490 self.sparse_range(ns_idx) 491 ); 492 self.sparse_indices[sparse_index] 493 }; 494 let key = FuncKey::from_parts(key_ns, key_index); 495 496 Some(key) 497 } 498 499 /// Whether the given kind's index space is (generally) densely populated 500 /// and therefore we should densely pack them in the table for `O(1)` 501 /// lookups; otherwise, we should avoid code size bloat by using the sparse 502 /// table indirection and `O(log n)` binary search lookups. 503 fn is_dense(kind: FuncKeyKind) -> bool { 504 match kind { 505 FuncKeyKind::DefinedWasmFunction 506 | FuncKeyKind::WasmToArrayTrampoline 507 | FuncKeyKind::PulleyHostCall => true, 508 509 FuncKeyKind::ArrayToWasmTrampoline | FuncKeyKind::WasmToBuiltinTrampoline => false, 510 511 #[cfg(feature = "component-model")] 512 FuncKeyKind::ComponentTrampoline 513 | FuncKeyKind::ResourceDropTrampoline 514 | FuncKeyKind::UnsafeIntrinsic => true, 515 } 516 } 517 518 /// Whether the given function kind has source locations or not. 519 fn has_src_locs(kind: FuncKeyKind) -> bool { 520 match kind { 521 FuncKeyKind::DefinedWasmFunction => true, 522 FuncKeyKind::ArrayToWasmTrampoline 523 | FuncKeyKind::WasmToArrayTrampoline 524 | FuncKeyKind::WasmToBuiltinTrampoline 525 | FuncKeyKind::PulleyHostCall => false, 526 #[cfg(feature = "component-model")] 527 FuncKeyKind::ComponentTrampoline 528 | FuncKeyKind::ResourceDropTrampoline 529 | FuncKeyKind::UnsafeIntrinsic => false, 530 } 531 } 532 } 533 534 /// Secondary in-memory results of module compilation. 535 /// 536 /// This opaque structure can be optionally passed back to 537 /// `CompiledModule::from_artifacts` to avoid decoding extra information there. 538 #[derive(Serialize, Deserialize)] 539 pub struct CompiledModuleInfo { 540 /// Type information about the compiled WebAssembly module. 541 pub module: Module, 542 543 /// General compilation metadata. 544 pub meta: Metadata, 545 546 /// Sorted list, by function index, of names we have for this module. 547 pub func_names: Vec<FunctionName>, 548 } 549 550 /// The name of a function stored in the 551 /// [`ELF_NAME_DATA`](crate::obj::ELF_NAME_DATA) section. 552 #[derive(Serialize, Deserialize)] 553 pub struct FunctionName { 554 /// The Wasm function index of this function. 555 pub idx: FuncIndex, 556 /// The offset of the name in the 557 /// [`ELF_NAME_DATA`](crate::obj::ELF_NAME_DATA) section. 558 pub offset: u32, 559 /// The length of the name in bytes. 560 pub len: u32, 561 } 562 563 /// Metadata associated with a compiled ELF artifact. 564 #[derive(Serialize, Deserialize)] 565 pub struct Metadata { 566 /// Whether or not the original wasm module contained debug information that 567 /// we skipped and did not parse. 568 pub has_unparsed_debuginfo: bool, 569 570 /// Offset in the original wasm file to the code section. 571 pub code_section_offset: u64, 572 573 /// Whether or not custom wasm-specific dwarf sections were inserted into 574 /// the ELF image. 575 /// 576 /// Note that even if this flag is `true` sections may be missing if they 577 /// weren't found in the original wasm module itself. 578 pub has_wasm_debuginfo: bool, 579 580 /// Dwarf sections and the offsets at which they're stored in the 581 /// ELF_WASMTIME_DWARF 582 pub dwarf: Vec<(u8, Range<u64>)>, 583 } 584 585 /// Value of a configured setting for a [`Compiler`](crate::Compiler) 586 #[derive(Serialize, Deserialize, Hash, Eq, PartialEq, Debug)] 587 pub enum FlagValue<'a> { 588 /// Name of the value that has been configured for this setting. 589 Enum(&'a str), 590 /// The numerical value of the configured settings. 591 Num(u8), 592 /// Whether the setting is on or off. 593 Bool(bool), 594 } 595 596 impl fmt::Display for FlagValue<'_> { 597 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 598 match self { 599 Self::Enum(v) => v.fmt(f), 600 Self::Num(v) => v.fmt(f), 601 Self::Bool(v) => v.fmt(f), 602 } 603 } 604 } 605 606 /// Types of objects that can be created by `Compiler::object` 607 pub enum ObjectKind { 608 /// A core wasm compilation artifact 609 Module, 610 /// A component compilation artifact 611 Component, 612 } 613 614 #[cfg(test)] 615 mod tests { 616 use super::*; 617 use crate::{DefinedFuncIndex, StaticModuleIndex}; 618 619 fn func_loc(range: Range<u32>) -> FunctionLoc { 620 FunctionLoc { 621 start: range.start, 622 length: range.end - range.start, 623 } 624 } 625 626 fn def_func_key(m: u32, f: u32) -> FuncKey { 627 FuncKey::DefinedWasmFunction( 628 StaticModuleIndex::from_u32(m), 629 DefinedFuncIndex::from_u32(f), 630 ) 631 } 632 633 fn array_to_wasm_tramp_key(m: u32, f: u32) -> FuncKey { 634 FuncKey::ArrayToWasmTrampoline( 635 StaticModuleIndex::from_u32(m), 636 DefinedFuncIndex::from_u32(f), 637 ) 638 } 639 640 fn make_test_table() -> CompiledFunctionsTable { 641 let mut builder = CompiledFunctionsTableBuilder::new(); 642 643 builder 644 // ========= Dense ========= 645 .push_func(def_func_key(0, 0), func_loc(0..10), FilePos::new(111)) 646 .push_func(def_func_key(0, 1), func_loc(10..20), FilePos::new(222)) 647 .push_func(def_func_key(0, 2), func_loc(20..30), FilePos::none()) 648 // Gap in dense keys! 649 .push_func(def_func_key(0, 5), func_loc(30..40), FilePos::new(333)) 650 // ========= Sparse ========= 651 .push_func( 652 array_to_wasm_tramp_key(0, 1), 653 func_loc(100..110), 654 FilePos::none(), 655 ) 656 .push_func( 657 array_to_wasm_tramp_key(0, 2), 658 func_loc(110..120), 659 FilePos::none(), 660 ) 661 .push_func( 662 array_to_wasm_tramp_key(0, 5), 663 func_loc(120..130), 664 FilePos::none(), 665 ); 666 667 builder.finish() 668 } 669 670 #[test] 671 fn src_locs() { 672 let table = make_test_table(); 673 674 for (key, expected) in [ 675 (def_func_key(0, 0), Some(FilePos::new(111))), 676 (def_func_key(0, 1), Some(FilePos::new(222))), 677 (def_func_key(0, 2), None), 678 (def_func_key(0, 3), None), 679 (def_func_key(0, 4), None), 680 (def_func_key(0, 5), Some(FilePos::new(333))), 681 (array_to_wasm_tramp_key(0, 0), None), 682 (array_to_wasm_tramp_key(0, 1), None), 683 (array_to_wasm_tramp_key(0, 2), None), 684 (array_to_wasm_tramp_key(0, 3), None), 685 (array_to_wasm_tramp_key(0, 4), None), 686 (array_to_wasm_tramp_key(0, 5), None), 687 ] { 688 eprintln!("Checking key {key:?}"); 689 let actual = table.src_loc(key); 690 assert_eq!(expected, actual); 691 } 692 } 693 694 #[test] 695 fn func_locs() { 696 let table = make_test_table(); 697 698 for (key, expected) in [ 699 (def_func_key(0, 0), Some(0)), 700 (def_func_key(0, 1), Some(10)), 701 (def_func_key(0, 2), Some(20)), 702 (def_func_key(0, 3), None), 703 (def_func_key(0, 4), None), 704 (def_func_key(0, 5), Some(30)), 705 (array_to_wasm_tramp_key(0, 0), None), 706 (array_to_wasm_tramp_key(0, 1), Some(100)), 707 (array_to_wasm_tramp_key(0, 2), Some(110)), 708 (array_to_wasm_tramp_key(0, 3), None), 709 (array_to_wasm_tramp_key(0, 4), None), 710 (array_to_wasm_tramp_key(0, 5), Some(120)), 711 ] { 712 let actual = table.func_loc(key); 713 match (expected, actual) { 714 (None, None) => {} 715 (Some(expected), Some(actual)) => assert_eq!(expected, actual.start), 716 (None, Some(actual)) => { 717 panic!("expected no function location for {key:?}, got {actual:?}") 718 } 719 (Some(_), None) => { 720 panic!("expected a function location for {key:?}, but got nothing") 721 } 722 } 723 } 724 } 725 726 #[test] 727 fn reverse_func_locs() { 728 let table = make_test_table(); 729 730 for (range, expected) in [ 731 (0..10, Some(def_func_key(0, 0))), 732 (10..20, Some(def_func_key(0, 1))), 733 (20..30, Some(def_func_key(0, 2))), 734 (30..40, Some(def_func_key(0, 5))), 735 (40..100, None), 736 (100..110, Some(array_to_wasm_tramp_key(0, 1))), 737 (110..120, Some(array_to_wasm_tramp_key(0, 2))), 738 (120..130, Some(array_to_wasm_tramp_key(0, 5))), 739 (140..150, None), 740 ] { 741 for i in range { 742 eprintln!("Checking offset {i}"); 743 let actual = table.func_by_text_offset(i); 744 assert_eq!(expected, actual); 745 } 746 } 747 } 748 749 #[test] 750 fn reverse_lookups() { 751 use arbitrary::{Result, Unstructured}; 752 753 arbtest::arbtest(|u| run(u)).budget_ms(1_000); 754 755 fn run(u: &mut Unstructured<'_>) -> Result<()> { 756 let mut funcs = Vec::new(); 757 758 // Build up a random set of functions with random indices. 759 for _ in 0..u.int_in_range(1..=200)? { 760 let key = match u.int_in_range(0..=6)? { 761 0 => FuncKey::DefinedWasmFunction(idx(u, 10)?, idx(u, 200)?), 762 1 => FuncKey::ArrayToWasmTrampoline(idx(u, 10)?, idx(u, 200)?), 763 2 => FuncKey::WasmToArrayTrampoline(idx(u, 100)?), 764 3 => FuncKey::WasmToBuiltinTrampoline(u.arbitrary()?), 765 4 => FuncKey::PulleyHostCall(u.arbitrary()?), 766 5 => FuncKey::ComponentTrampoline(u.arbitrary()?, idx(u, 50)?), 767 6 => FuncKey::ResourceDropTrampoline, 768 _ => unreachable!(), 769 }; 770 funcs.push(key); 771 } 772 773 // Sort/dedup our list of `funcs` to satisfy the requirement of 774 // `CompiledFunctionsTableBuilder::push_func`. 775 funcs.sort(); 776 funcs.dedup(); 777 778 let mut builder = CompiledFunctionsTableBuilder::new(); 779 let mut size = 0; 780 let mut expected = Vec::new(); 781 for key in funcs { 782 let length = u.int_in_range(1..=10)?; 783 for _ in 0..length { 784 expected.push(key); 785 } 786 // println!("push {key:?} - {length}"); 787 builder.push_func( 788 key, 789 FunctionLoc { 790 start: size, 791 length, 792 }, 793 FilePos::none(), 794 ); 795 size += length; 796 } 797 let index = builder.finish(); 798 799 let mut expected = expected.iter(); 800 for i in 0..size { 801 // println!("lookup {i}"); 802 let actual = index.func_by_text_offset(i).unwrap(); 803 assert_eq!(Some(&actual), expected.next()); 804 } 805 806 Ok(()) 807 } 808 809 fn idx<T>(u: &mut Unstructured<'_>, max: usize) -> Result<T> 810 where 811 T: EntityRef, 812 { 813 Ok(T::new(u.int_in_range(0..=max - 1)?)) 814 } 815 } 816 } 817