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