1use crate::prelude::*;
5use crate::{FilePos, FuncIndex, FuncKey, FuncKeyIndex, FuncKeyKind, FuncKeyNamespace, Module};
6use core::ops::Range;
7use core::{fmt, u32};
8use core::{iter, str};
9use cranelift_entity::{EntityRef, PrimaryMap};
10use serde_derive::{Deserialize, Serialize};
11
12#[derive(Copy, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
15pub struct FunctionLoc {
16 pub start: u32,
19 pub length: u32,
21}
22
23impl FunctionLoc {
24 #[inline]
26 pub fn is_empty(&self) -> bool {
27 self.length == 0
28 }
29}
30
31pub struct CompiledFunctionsTableBuilder {
33 inner: CompiledFunctionsTable,
34}
35
36impl CompiledFunctionsTableBuilder {
37 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 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 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 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 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 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 pub fn finish(self) -> CompiledFunctionsTable {
191 self.inner
192 }
193}
194
195#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
196struct NamespaceIndex(u32);
197cranelift_entity::entity_impl!(NamespaceIndex);
198
199#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
200struct FuncLocIndex(u32);
201cranelift_entity::entity_impl!(FuncLocIndex);
202
203#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
204struct SparseIndex(u32);
205cranelift_entity::entity_impl!(SparseIndex);
206
207#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
208struct SrcLocIndex(u32);
209cranelift_entity::entity_impl!(SrcLocIndex);
210
211#[derive(Debug, Serialize, Deserialize)]
243pub struct CompiledFunctionsTable {
244 namespaces: PrimaryMap<NamespaceIndex, FuncKeyNamespace>,
249
250 func_loc_starts: PrimaryMap<NamespaceIndex, FuncLocIndex>,
257
258 sparse_starts: PrimaryMap<NamespaceIndex, SparseIndex>,
267
268 src_loc_starts: PrimaryMap<NamespaceIndex, SrcLocIndex>,
278
279 sparse_indices: PrimaryMap<SparseIndex, FuncKeyIndex>,
287
288 func_locs: PrimaryMap<FuncLocIndex, FunctionLoc>,
298
299 src_locs: PrimaryMap<SrcLocIndex, FilePos>,
305}
306
307impl 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 #[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 #[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 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 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 Ok(k) => k,
439 Err(k) => k,
444 };
445 let index = FuncLocIndex::new(index);
446
447 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 Ok(i) => i,
465 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 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 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#[derive(Serialize, Deserialize)]
539pub struct CompiledModuleInfo {
540 pub module: Module,
542
543 pub meta: Metadata,
545
546 pub func_names: Vec<FunctionName>,
548}
549
550#[derive(Serialize, Deserialize)]
553pub struct FunctionName {
554 pub idx: FuncIndex,
556 pub offset: u32,
559 pub len: u32,
561}
562
563#[derive(Serialize, Deserialize)]
565pub struct Metadata {
566 pub has_unparsed_debuginfo: bool,
569
570 pub code_section_offset: u64,
572
573 pub has_wasm_debuginfo: bool,
579
580 pub dwarf: Vec<(u8, Range<u64>)>,
583}
584
585#[derive(Serialize, Deserialize, Hash, Eq, PartialEq, Debug)]
587pub enum FlagValue<'a> {
588 Enum(&'a str),
590 Num(u8),
592 Bool(bool),
594}
595
596impl 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
606pub enum ObjectKind {
608 Module,
610 Component,
612}
613
614#[cfg(test)]
615mod 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 .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 .push_func(def_func_key(0, 5), func_loc(30..40), FilePos::new(333))
650 .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 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 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 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 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}