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 | FuncKeyKind::ResourceDropTrampoline => true, 513 } 514 } 515 516 /// Whether the given function kind has source locations or not. 517 fn has_src_locs(kind: FuncKeyKind) -> bool { 518 match kind { 519 FuncKeyKind::DefinedWasmFunction => true, 520 FuncKeyKind::ArrayToWasmTrampoline 521 | FuncKeyKind::WasmToArrayTrampoline 522 | FuncKeyKind::WasmToBuiltinTrampoline 523 | FuncKeyKind::PulleyHostCall => false, 524 #[cfg(feature = "component-model")] 525 FuncKeyKind::ComponentTrampoline | FuncKeyKind::ResourceDropTrampoline => false, 526 } 527 } 528 } 529 530 /// Secondary in-memory results of module compilation. 531 /// 532 /// This opaque structure can be optionally passed back to 533 /// `CompiledModule::from_artifacts` to avoid decoding extra information there. 534 #[derive(Serialize, Deserialize)] 535 pub struct CompiledModuleInfo { 536 /// Type information about the compiled WebAssembly module. 537 pub module: Module, 538 539 /// General compilation metadata. 540 pub meta: Metadata, 541 542 /// Sorted list, by function index, of names we have for this module. 543 pub func_names: Vec<FunctionName>, 544 } 545 546 /// The name of a function stored in the 547 /// [`ELF_NAME_DATA`](crate::obj::ELF_NAME_DATA) section. 548 #[derive(Serialize, Deserialize)] 549 pub struct FunctionName { 550 /// The Wasm function index of this function. 551 pub idx: FuncIndex, 552 /// The offset of the name in the 553 /// [`ELF_NAME_DATA`](crate::obj::ELF_NAME_DATA) section. 554 pub offset: u32, 555 /// The length of the name in bytes. 556 pub len: u32, 557 } 558 559 /// Metadata associated with a compiled ELF artifact. 560 #[derive(Serialize, Deserialize)] 561 pub struct Metadata { 562 /// Whether or not the original wasm module contained debug information that 563 /// we skipped and did not parse. 564 pub has_unparsed_debuginfo: bool, 565 566 /// Offset in the original wasm file to the code section. 567 pub code_section_offset: u64, 568 569 /// Whether or not custom wasm-specific dwarf sections were inserted into 570 /// the ELF image. 571 /// 572 /// Note that even if this flag is `true` sections may be missing if they 573 /// weren't found in the original wasm module itself. 574 pub has_wasm_debuginfo: bool, 575 576 /// Dwarf sections and the offsets at which they're stored in the 577 /// ELF_WASMTIME_DWARF 578 pub dwarf: Vec<(u8, Range<u64>)>, 579 } 580 581 /// Value of a configured setting for a [`Compiler`](crate::Compiler) 582 #[derive(Serialize, Deserialize, Hash, Eq, PartialEq, Debug)] 583 pub enum FlagValue<'a> { 584 /// Name of the value that has been configured for this setting. 585 Enum(&'a str), 586 /// The numerical value of the configured settings. 587 Num(u8), 588 /// Whether the setting is on or off. 589 Bool(bool), 590 } 591 592 impl fmt::Display for FlagValue<'_> { 593 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 594 match self { 595 Self::Enum(v) => v.fmt(f), 596 Self::Num(v) => v.fmt(f), 597 Self::Bool(v) => v.fmt(f), 598 } 599 } 600 } 601 602 /// Types of objects that can be created by `Compiler::object` 603 pub enum ObjectKind { 604 /// A core wasm compilation artifact 605 Module, 606 /// A component compilation artifact 607 Component, 608 } 609 610 #[cfg(test)] 611 mod tests { 612 use super::*; 613 use crate::{DefinedFuncIndex, StaticModuleIndex}; 614 615 fn func_loc(range: Range<u32>) -> FunctionLoc { 616 FunctionLoc { 617 start: range.start, 618 length: range.end - range.start, 619 } 620 } 621 622 fn def_func_key(m: u32, f: u32) -> FuncKey { 623 FuncKey::DefinedWasmFunction( 624 StaticModuleIndex::from_u32(m), 625 DefinedFuncIndex::from_u32(f), 626 ) 627 } 628 629 fn array_to_wasm_tramp_key(m: u32, f: u32) -> FuncKey { 630 FuncKey::ArrayToWasmTrampoline( 631 StaticModuleIndex::from_u32(m), 632 DefinedFuncIndex::from_u32(f), 633 ) 634 } 635 636 fn make_test_table() -> CompiledFunctionsTable { 637 let mut builder = CompiledFunctionsTableBuilder::new(); 638 639 builder 640 // ========= Dense ========= 641 .push_func(def_func_key(0, 0), func_loc(0..10), FilePos::new(111)) 642 .push_func(def_func_key(0, 1), func_loc(10..20), FilePos::new(222)) 643 .push_func(def_func_key(0, 2), func_loc(20..30), FilePos::none()) 644 // Gap in dense keys! 645 .push_func(def_func_key(0, 5), func_loc(30..40), FilePos::new(333)) 646 // ========= Sparse ========= 647 .push_func( 648 array_to_wasm_tramp_key(0, 1), 649 func_loc(100..110), 650 FilePos::none(), 651 ) 652 .push_func( 653 array_to_wasm_tramp_key(0, 2), 654 func_loc(110..120), 655 FilePos::none(), 656 ) 657 .push_func( 658 array_to_wasm_tramp_key(0, 5), 659 func_loc(120..130), 660 FilePos::none(), 661 ); 662 663 builder.finish() 664 } 665 666 #[test] 667 fn src_locs() { 668 let table = make_test_table(); 669 670 for (key, expected) in [ 671 (def_func_key(0, 0), Some(FilePos::new(111))), 672 (def_func_key(0, 1), Some(FilePos::new(222))), 673 (def_func_key(0, 2), None), 674 (def_func_key(0, 3), None), 675 (def_func_key(0, 4), None), 676 (def_func_key(0, 5), Some(FilePos::new(333))), 677 (array_to_wasm_tramp_key(0, 0), None), 678 (array_to_wasm_tramp_key(0, 1), None), 679 (array_to_wasm_tramp_key(0, 2), None), 680 (array_to_wasm_tramp_key(0, 3), None), 681 (array_to_wasm_tramp_key(0, 4), None), 682 (array_to_wasm_tramp_key(0, 5), None), 683 ] { 684 eprintln!("Checking key {key:?}"); 685 let actual = table.src_loc(key); 686 assert_eq!(expected, actual); 687 } 688 } 689 690 #[test] 691 fn func_locs() { 692 let table = make_test_table(); 693 694 for (key, expected) in [ 695 (def_func_key(0, 0), Some(0)), 696 (def_func_key(0, 1), Some(10)), 697 (def_func_key(0, 2), Some(20)), 698 (def_func_key(0, 3), None), 699 (def_func_key(0, 4), None), 700 (def_func_key(0, 5), Some(30)), 701 (array_to_wasm_tramp_key(0, 0), None), 702 (array_to_wasm_tramp_key(0, 1), Some(100)), 703 (array_to_wasm_tramp_key(0, 2), Some(110)), 704 (array_to_wasm_tramp_key(0, 3), None), 705 (array_to_wasm_tramp_key(0, 4), None), 706 (array_to_wasm_tramp_key(0, 5), Some(120)), 707 ] { 708 let actual = table.func_loc(key); 709 match (expected, actual) { 710 (None, None) => {} 711 (Some(expected), Some(actual)) => assert_eq!(expected, actual.start), 712 (None, Some(actual)) => { 713 panic!("expected no function location for {key:?}, got {actual:?}") 714 } 715 (Some(_), None) => { 716 panic!("expected a function location for {key:?}, but got nothing") 717 } 718 } 719 } 720 } 721 722 #[test] 723 fn reverse_func_locs() { 724 let table = make_test_table(); 725 726 for (range, expected) in [ 727 (0..10, Some(def_func_key(0, 0))), 728 (10..20, Some(def_func_key(0, 1))), 729 (20..30, Some(def_func_key(0, 2))), 730 (30..40, Some(def_func_key(0, 5))), 731 (40..100, None), 732 (100..110, Some(array_to_wasm_tramp_key(0, 1))), 733 (110..120, Some(array_to_wasm_tramp_key(0, 2))), 734 (120..130, Some(array_to_wasm_tramp_key(0, 5))), 735 (140..150, None), 736 ] { 737 for i in range { 738 eprintln!("Checking offset {i}"); 739 let actual = table.func_by_text_offset(i); 740 assert_eq!(expected, actual); 741 } 742 } 743 } 744 745 #[test] 746 fn reverse_lookups() { 747 use arbitrary::{Result, Unstructured}; 748 749 arbtest::arbtest(|u| run(u)).budget_ms(1_000); 750 751 fn run(u: &mut Unstructured<'_>) -> Result<()> { 752 let mut funcs = Vec::new(); 753 754 // Build up a random set of functions with random indices. 755 for _ in 0..u.int_in_range(1..=200)? { 756 let key = match u.int_in_range(0..=6)? { 757 0 => FuncKey::DefinedWasmFunction(idx(u, 10)?, idx(u, 200)?), 758 1 => FuncKey::ArrayToWasmTrampoline(idx(u, 10)?, idx(u, 200)?), 759 2 => FuncKey::WasmToArrayTrampoline(idx(u, 100)?), 760 3 => FuncKey::WasmToBuiltinTrampoline(u.arbitrary()?), 761 4 => FuncKey::PulleyHostCall(u.arbitrary()?), 762 5 => FuncKey::ComponentTrampoline(u.arbitrary()?, idx(u, 50)?), 763 6 => FuncKey::ResourceDropTrampoline, 764 _ => unreachable!(), 765 }; 766 funcs.push(key); 767 } 768 769 // Sort/dedup our list of `funcs` to satisfy the requirement of 770 // `CompiledFunctionsTableBuilder::push_func`. 771 funcs.sort(); 772 funcs.dedup(); 773 774 let mut builder = CompiledFunctionsTableBuilder::new(); 775 let mut size = 0; 776 let mut expected = Vec::new(); 777 for key in funcs { 778 let length = u.int_in_range(1..=10)?; 779 for _ in 0..length { 780 expected.push(key); 781 } 782 // println!("push {key:?} - {length}"); 783 builder.push_func( 784 key, 785 FunctionLoc { 786 start: size, 787 length, 788 }, 789 FilePos::none(), 790 ); 791 size += length; 792 } 793 let index = builder.finish(); 794 795 let mut expected = expected.iter(); 796 for i in 0..size { 797 // println!("lookup {i}"); 798 let actual = index.func_by_text_offset(i).unwrap(); 799 assert_eq!(Some(&actual), expected.next()); 800 } 801 802 Ok(()) 803 } 804 805 fn idx<T>(u: &mut Unstructured<'_>, max: usize) -> Result<T> 806 where 807 T: EntityRef, 808 { 809 Ok(T::new(u.int_in_range(0..=max - 1)?)) 810 } 811 } 812 } 813