wasm_bindgen_cli_support/
lib.rs

1use anyhow::{bail, Context, Error};
2use std::collections::{BTreeMap, HashMap, HashSet};
3use std::env;
4use std::fs;
5use std::mem;
6use std::path::{Path, PathBuf};
7use std::str;
8use walrus::Module;
9
10pub(crate) const PLACEHOLDER_MODULE: &str = "__wbindgen_placeholder__";
11
12mod decode;
13mod descriptor;
14mod descriptors;
15mod externref;
16mod interpreter;
17mod intrinsic;
18mod js;
19mod multivalue;
20mod transforms;
21pub mod wasm2es6js;
22mod wasm_conventions;
23mod wit;
24
25pub struct Bindgen {
26    input: Input,
27    out_name: Option<String>,
28    mode: OutputMode,
29    debug: bool,
30    typescript: bool,
31    omit_imports: bool,
32    demangle: bool,
33    keep_lld_exports: bool,
34    keep_debug: bool,
35    remove_name_section: bool,
36    remove_producers_section: bool,
37    omit_default_module_path: bool,
38    emit_start: bool,
39    externref: bool,
40    multi_value: bool,
41    encode_into: EncodeInto,
42    split_linked_modules: bool,
43    symbol_dispose: bool,
44}
45
46pub struct Output {
47    module: walrus::Module,
48    stem: String,
49    generated: Generated,
50}
51
52struct Generated {
53    mode: OutputMode,
54    js: String,
55    ts: String,
56    start: Option<String>,
57    snippets: HashMap<String, Vec<String>>,
58    local_modules: HashMap<String, String>,
59    npm_dependencies: HashMap<String, (PathBuf, String)>,
60    typescript: bool,
61}
62
63#[derive(Clone)]
64enum OutputMode {
65    Bundler { browser_only: bool },
66    Web,
67    NoModules { global: String },
68    Node { module: bool },
69    Deno,
70}
71
72enum Input {
73    Path(PathBuf),
74    Module(Module, String),
75    Bytes(Vec<u8>, String),
76    None,
77}
78
79pub enum EncodeInto {
80    Test,
81    Always,
82    Never,
83}
84
85impl Bindgen {
86    pub fn new() -> Bindgen {
87        let externref =
88            env::var("WASM_BINDGEN_ANYREF").is_ok() || env::var("WASM_BINDGEN_EXTERNREF").is_ok();
89        let multi_value = env::var("WASM_BINDGEN_MULTI_VALUE").is_ok();
90        let symbol_dispose = env::var("WASM_BINDGEN_EXPERIMENTAL_SYMBOL_DISPOSE").is_ok();
91        Bindgen {
92            input: Input::None,
93            out_name: None,
94            mode: OutputMode::Bundler {
95                browser_only: false,
96            },
97            debug: false,
98            typescript: false,
99            omit_imports: false,
100            demangle: true,
101            keep_lld_exports: false,
102            keep_debug: false,
103            remove_name_section: false,
104            remove_producers_section: false,
105            emit_start: true,
106            externref,
107            multi_value,
108            encode_into: EncodeInto::Test,
109            omit_default_module_path: true,
110            split_linked_modules: false,
111            symbol_dispose,
112        }
113    }
114
115    pub fn input_path<P: AsRef<Path>>(&mut self, path: P) -> &mut Bindgen {
116        self.input = Input::Path(path.as_ref().to_path_buf());
117        self
118    }
119
120    pub fn out_name(&mut self, name: &str) -> &mut Bindgen {
121        self.out_name = Some(name.to_string());
122        self
123    }
124
125    #[deprecated = "automatically detected via `-Ctarget-feature=+reference-types`"]
126    pub fn reference_types(&mut self, enable: bool) -> &mut Bindgen {
127        self.externref = enable;
128        self
129    }
130
131    /// Explicitly specify the already parsed input module.
132    pub fn input_module(&mut self, name: &str, module: Module) -> &mut Bindgen {
133        let name = name.to_string();
134        self.input = Input::Module(module, name);
135        self
136    }
137
138    /// Specify the input as the provided Wasm bytes.
139    pub fn input_bytes(&mut self, name: &str, bytes: Vec<u8>) -> &mut Bindgen {
140        let name = name.to_string();
141        self.input = Input::Bytes(bytes, name);
142        self
143    }
144
145    fn switch_mode(&mut self, mode: OutputMode, flag: &str) -> Result<(), Error> {
146        match self.mode {
147            OutputMode::Bundler { .. } => self.mode = mode,
148            _ => bail!(
149                "cannot specify `{}` with another output mode already specified",
150                flag
151            ),
152        }
153        Ok(())
154    }
155
156    pub fn nodejs(&mut self, node: bool) -> Result<&mut Bindgen, Error> {
157        if node {
158            self.switch_mode(OutputMode::Node { module: false }, "--target nodejs")?;
159        }
160        Ok(self)
161    }
162
163    pub fn nodejs_module(&mut self, node: bool) -> Result<&mut Bindgen, Error> {
164        if node {
165            self.switch_mode(
166                OutputMode::Node { module: true },
167                "--target experimental-nodejs-module",
168            )?;
169        }
170        Ok(self)
171    }
172
173    pub fn bundler(&mut self, bundler: bool) -> Result<&mut Bindgen, Error> {
174        if bundler {
175            self.switch_mode(
176                OutputMode::Bundler {
177                    browser_only: false,
178                },
179                "--target bundler",
180            )?;
181        }
182        Ok(self)
183    }
184
185    pub fn web(&mut self, web: bool) -> Result<&mut Bindgen, Error> {
186        if web {
187            self.switch_mode(OutputMode::Web, "--target web")?;
188        }
189        Ok(self)
190    }
191
192    pub fn no_modules(&mut self, no_modules: bool) -> Result<&mut Bindgen, Error> {
193        if no_modules {
194            self.switch_mode(
195                OutputMode::NoModules {
196                    global: "wasm_bindgen".to_string(),
197                },
198                "--target no-modules",
199            )?;
200        }
201        Ok(self)
202    }
203
204    pub fn browser(&mut self, browser: bool) -> Result<&mut Bindgen, Error> {
205        if browser {
206            match &mut self.mode {
207                OutputMode::Bundler { browser_only } => *browser_only = true,
208                _ => bail!("cannot specify `--browser` with other output types"),
209            }
210        }
211        Ok(self)
212    }
213
214    pub fn deno(&mut self, deno: bool) -> Result<&mut Bindgen, Error> {
215        if deno {
216            self.switch_mode(OutputMode::Deno, "--target deno")?;
217            self.encode_into(EncodeInto::Always);
218        }
219        Ok(self)
220    }
221
222    pub fn no_modules_global(&mut self, name: &str) -> Result<&mut Bindgen, Error> {
223        match &mut self.mode {
224            OutputMode::NoModules { global } => *global = name.to_string(),
225            _ => bail!("can only specify `--no-modules-global` with `--target no-modules`"),
226        }
227        Ok(self)
228    }
229
230    pub fn debug(&mut self, debug: bool) -> &mut Bindgen {
231        self.debug = debug;
232        self
233    }
234
235    pub fn typescript(&mut self, typescript: bool) -> &mut Bindgen {
236        self.typescript = typescript;
237        self
238    }
239
240    pub fn omit_imports(&mut self, omit_imports: bool) -> &mut Bindgen {
241        self.omit_imports = omit_imports;
242        self
243    }
244
245    pub fn demangle(&mut self, demangle: bool) -> &mut Bindgen {
246        self.demangle = demangle;
247        self
248    }
249
250    pub fn keep_lld_exports(&mut self, keep_lld_exports: bool) -> &mut Bindgen {
251        self.keep_lld_exports = keep_lld_exports;
252        self
253    }
254
255    pub fn keep_debug(&mut self, keep_debug: bool) -> &mut Bindgen {
256        self.keep_debug = keep_debug;
257        self
258    }
259
260    pub fn remove_name_section(&mut self, remove: bool) -> &mut Bindgen {
261        self.remove_name_section = remove;
262        self
263    }
264
265    pub fn remove_producers_section(&mut self, remove: bool) -> &mut Bindgen {
266        self.remove_producers_section = remove;
267        self
268    }
269
270    pub fn emit_start(&mut self, emit: bool) -> &mut Bindgen {
271        self.emit_start = emit;
272        self
273    }
274
275    pub fn encode_into(&mut self, mode: EncodeInto) -> &mut Bindgen {
276        self.encode_into = mode;
277        self
278    }
279
280    pub fn omit_default_module_path(&mut self, omit_default_module_path: bool) -> &mut Bindgen {
281        self.omit_default_module_path = omit_default_module_path;
282        self
283    }
284
285    pub fn split_linked_modules(&mut self, split_linked_modules: bool) -> &mut Bindgen {
286        self.split_linked_modules = split_linked_modules;
287        self
288    }
289
290    pub fn generate<P: AsRef<Path>>(&mut self, path: P) -> Result<(), Error> {
291        self.generate_output()?.emit(path.as_ref())
292    }
293
294    pub fn stem(&self) -> Result<&str, Error> {
295        Ok(match &self.input {
296            Input::None => bail!("must have an input by now"),
297            Input::Module(_, name) | Input::Bytes(_, name) => name,
298            Input::Path(path) => match &self.out_name {
299                Some(name) => name,
300                None => path.file_stem().unwrap().to_str().unwrap(),
301            },
302        })
303    }
304
305    pub fn generate_output(&mut self) -> Result<Output, Error> {
306        let mut module = match self.input {
307            Input::None => bail!("must have an input by now"),
308            Input::Module(ref mut m, _) => {
309                let blank_module = Module::default();
310                mem::replace(m, blank_module)
311            }
312            Input::Path(ref path) => {
313                let bytes = std::fs::read(path)
314                    .with_context(|| format!("failed reading '{}'", path.display()))?;
315                self.module_from_bytes(&bytes).with_context(|| {
316                    format!("failed getting Wasm module for '{}'", path.display())
317                })?
318            }
319            Input::Bytes(ref bytes, _) => self
320                .module_from_bytes(bytes)
321                .context("failed getting Wasm module")?,
322        };
323
324        // Enable reference type transformations if the module is already using it.
325        if let Ok(true) = wasm_conventions::target_feature(&module, "reference-types") {
326            self.externref = true;
327        }
328
329        // Enable multivalue transformations if the module is already using it.
330        if let Ok(true) = wasm_conventions::target_feature(&module, "multivalue") {
331            self.multi_value = true;
332        }
333
334        // Check that no exported symbol is called "default" if we target web.
335        if matches!(self.mode, OutputMode::Web)
336            && module.exports.iter().any(|export| export.name == "default")
337        {
338            bail!("exported symbol \"default\" not allowed for --target web")
339        }
340
341        let thread_count = transforms::threads::run(&mut module)
342            .with_context(|| "failed to prepare module for threading")?;
343
344        // If requested, turn all mangled symbols into prettier unmangled
345        // symbols with the help of `rustc-demangle`.
346        if self.demangle {
347            demangle(&mut module);
348        }
349        if !self.keep_lld_exports {
350            unexported_unused_lld_things(&mut module);
351        }
352
353        // We're making quite a few changes, list ourselves as a producer.
354        module
355            .producers
356            .add_processed_by("wasm-bindgen", &wasm_bindgen_shared::version());
357
358        // Parse and remove our custom section before executing descriptors.
359        // That includes checking that the binary has the same schema version
360        // as this version of the CLI, which is why we do it first - to make
361        // sure that this binary was produced by a compatible version of the
362        // wasm-bindgen macro before attempting to interpret our unstable
363        // descriptor format. That way, we give a more helpful version mismatch
364        // error instead of an unhelpful panic if an incompatible descriptor is
365        // found.
366        let mut storage = Vec::new();
367        let programs = wit::extract_programs(&mut module, &mut storage)?;
368
369        // Learn about the type signatures of all wasm-bindgen imports and
370        // exports by executing `__wbindgen_describe_*` functions. This'll
371        // effectively move all the descriptor functions to their own custom
372        // sections.
373        descriptors::execute(&mut module)?;
374
375        // Process the custom section we extracted earlier. In its stead insert
376        // a forward-compatible Wasm interface types section as well as an
377        // auxiliary section for all sorts of miscellaneous information and
378        // features #[wasm_bindgen] supports that aren't covered by wasm
379        // interface types.
380        wit::process(self, &mut module, programs, thread_count)?;
381
382        // Now that we've got type information from the webidl processing pass,
383        // touch up the output of rustc to insert externref shims where necessary.
384        // This is only done if the externref pass is enabled, which it's
385        // currently off-by-default since `externref` is still in development in
386        // engines.
387        //
388        // If the externref pass isn't necessary, then we blanket delete the
389        // export of all our externref intrinsics which will get cleaned up in the
390        // GC pass before JS generation.
391        if self.externref {
392            externref::process(&mut module)?;
393        } else {
394            let ids = module
395                .exports
396                .iter()
397                .filter(|e| e.name.starts_with("__externref"))
398                .map(|e| e.id())
399                .collect::<Vec<_>>();
400            for id in ids {
401                module.exports.delete(id);
402            }
403            // Clean up element segments as well if they have holes in them
404            // after some of our transformations, because non-externref engines
405            // only support contiguous arrays of function references in element
406            // segments.
407            externref::force_contiguous_elements(&mut module)?;
408        }
409
410        // Using all of our metadata convert our module to a multi-value using
411        // module if applicable.
412        if self.multi_value {
413            multivalue::run(&mut module)
414                .context("failed to transform return pointers into multi-value Wasm")?;
415        }
416
417        // We've done a whole bunch of transformations to the Wasm module, many
418        // of which leave "garbage" lying around, so let's prune out all our
419        // unnecessary things here.
420        gc_module_and_adapters(&mut module);
421
422        let stem = self.stem()?;
423
424        // Now we execute the JS generation passes to actually emit JS/TypeScript/etc.
425        let aux = module
426            .customs
427            .delete_typed::<wit::WasmBindgenAux>()
428            .expect("aux section should be present");
429        let adapters = module
430            .customs
431            .delete_typed::<wit::NonstandardWitSection>()
432            .unwrap();
433        let mut cx = js::Context::new(&mut module, self, &adapters, &aux)?;
434        cx.generate()?;
435        let (js, ts, start) = cx.finalize(stem)?;
436        let generated = Generated {
437            snippets: aux.snippets.clone(),
438            local_modules: aux.local_modules.clone(),
439            mode: self.mode.clone(),
440            typescript: self.typescript,
441            npm_dependencies: cx.npm_dependencies.clone(),
442            js,
443            ts,
444            start,
445        };
446
447        Ok(Output {
448            module,
449            stem: stem.to_string(),
450            generated,
451        })
452    }
453
454    fn module_from_bytes(&self, bytes: &[u8]) -> Result<Module, Error> {
455        walrus::ModuleConfig::new()
456            // Skip validation of the module as LLVM's output is
457            // generally already well-formed and so we won't gain much
458            // from re-validating. Additionally LLVM's current output
459            // for threads includes atomic instructions but doesn't
460            // include shared memory, so it fails that part of
461            // validation!
462            .strict_validate(false)
463            .generate_dwarf(self.keep_debug)
464            .generate_name_section(!self.remove_name_section)
465            .generate_producers_section(!self.remove_producers_section)
466            .parse(bytes)
467            .context("failed to parse input as wasm")
468    }
469
470    fn local_module_name(&self, module: &str) -> String {
471        format!("./snippets/{module}")
472    }
473
474    fn inline_js_module_name(
475        &self,
476        unique_crate_identifier: &str,
477        snippet_idx_in_crate: usize,
478    ) -> String {
479        format!("./snippets/{unique_crate_identifier}/inline{snippet_idx_in_crate}.js",)
480    }
481}
482
483fn reset_indentation(s: &str) -> String {
484    let mut indent: u32 = 0;
485    let mut dst = String::new();
486
487    fn is_doc_comment(line: &str) -> bool {
488        line.starts_with("*")
489    }
490
491    for line in s.lines() {
492        let line = line.trim();
493
494        // handle doc comments separately
495        if is_doc_comment(line) {
496            for _ in 0..indent {
497                dst.push_str("    ");
498            }
499            dst.push(' ');
500            dst.push_str(line);
501            dst.push('\n');
502            continue;
503        }
504
505        if line.starts_with('}') {
506            indent = indent.saturating_sub(1);
507        }
508
509        let extra = if line.starts_with(':') || line.starts_with('?') {
510            1
511        } else {
512            0
513        };
514        if !line.is_empty() {
515            for _ in 0..indent + extra {
516                dst.push_str("    ");
517            }
518            dst.push_str(line);
519        }
520        dst.push('\n');
521
522        if line.ends_with('{') {
523            indent += 1;
524        }
525    }
526    dst
527}
528
529fn demangle(module: &mut Module) {
530    for func in module.funcs.iter_mut() {
531        let name = match &func.name {
532            Some(name) => name,
533            None => continue,
534        };
535        if let Ok(sym) = rustc_demangle::try_demangle(name) {
536            func.name = Some(sym.to_string());
537        }
538    }
539}
540
541impl OutputMode {
542    fn uses_es_modules(&self) -> bool {
543        matches!(
544            self,
545            OutputMode::Bundler { .. }
546                | OutputMode::Web
547                | OutputMode::Node { module: true }
548                | OutputMode::Deno
549        )
550    }
551
552    fn nodejs(&self) -> bool {
553        matches!(self, OutputMode::Node { .. })
554    }
555
556    fn no_modules(&self) -> bool {
557        matches!(self, OutputMode::NoModules { .. })
558    }
559
560    fn esm_integration(&self) -> bool {
561        matches!(
562            self,
563            OutputMode::Bundler { .. } | OutputMode::Node { module: true }
564        )
565    }
566}
567
568/// Remove a number of internal exports that are synthesized by Rust's linker,
569/// LLD. These exports aren't typically ever needed and just add extra space to
570/// the binary.
571fn unexported_unused_lld_things(module: &mut Module) {
572    let mut to_remove = Vec::new();
573    for export in module.exports.iter() {
574        match export.name.as_str() {
575            "__heap_base" | "__data_end" | "__indirect_function_table" => {
576                to_remove.push(export.id());
577            }
578            _ => {}
579        }
580    }
581    for id in to_remove {
582        module.exports.delete(id);
583    }
584}
585
586impl Output {
587    pub fn js(&self) -> &str {
588        &self.generated.js
589    }
590
591    pub fn ts(&self) -> Option<&str> {
592        if self.generated.typescript {
593            Some(&self.generated.ts)
594        } else {
595            None
596        }
597    }
598
599    pub fn start(&self) -> Option<&String> {
600        self.generated.start.as_ref()
601    }
602
603    pub fn snippets(&self) -> &HashMap<String, Vec<String>> {
604        &self.generated.snippets
605    }
606
607    pub fn local_modules(&self) -> &HashMap<String, String> {
608        &self.generated.local_modules
609    }
610
611    pub fn npm_dependencies(&self) -> &HashMap<String, (PathBuf, String)> {
612        &self.generated.npm_dependencies
613    }
614
615    pub fn wasm(&self) -> &walrus::Module {
616        &self.module
617    }
618
619    pub fn wasm_mut(&mut self) -> &mut walrus::Module {
620        &mut self.module
621    }
622
623    pub fn emit(&mut self, out_dir: impl AsRef<Path>) -> Result<(), Error> {
624        self._emit(out_dir.as_ref())
625    }
626
627    fn _emit(&mut self, out_dir: &Path) -> Result<(), Error> {
628        let wasm_name = format!("{}_bg", self.stem);
629        let wasm_path = out_dir.join(&wasm_name).with_extension("wasm");
630        fs::create_dir_all(out_dir)?;
631        let wasm_bytes = self.module.emit_wasm();
632        fs::write(&wasm_path, wasm_bytes)
633            .with_context(|| format!("failed to write `{}`", wasm_path.display()))?;
634
635        let gen = &self.generated;
636
637        // Write out all local JS snippets to the final destination now that
638        // we've collected them from all the programs.
639        for (identifier, list) in gen.snippets.iter() {
640            for (i, js) in list.iter().enumerate() {
641                let name = format!("inline{i}.js");
642                let path = out_dir.join("snippets").join(identifier).join(name);
643                fs::create_dir_all(path.parent().unwrap())?;
644                fs::write(&path, js)
645                    .with_context(|| format!("failed to write `{}`", path.display()))?;
646            }
647        }
648
649        for (path, contents) in gen.local_modules.iter() {
650            let path = out_dir.join("snippets").join(path);
651            fs::create_dir_all(path.parent().unwrap())?;
652            fs::write(&path, contents)
653                .with_context(|| format!("failed to write `{}`", path.display()))?;
654        }
655
656        let is_genmode_nodemodule = matches!(gen.mode, OutputMode::Node { module: true });
657        if !gen.npm_dependencies.is_empty() || is_genmode_nodemodule {
658            #[derive(serde::Serialize)]
659            struct PackageJson<'a> {
660                #[serde(rename = "type", skip_serializing_if = "Option::is_none")]
661                ty: Option<&'static str>,
662                dependencies: BTreeMap<&'a str, &'a str>,
663            }
664            let pj = PackageJson {
665                ty: is_genmode_nodemodule.then_some("module"),
666                dependencies: gen
667                    .npm_dependencies
668                    .iter()
669                    .map(|(k, v)| (k.as_str(), v.1.as_str()))
670                    .collect(),
671            };
672            let json = serde_json::to_string_pretty(&pj)?;
673            fs::write(out_dir.join("package.json"), json)?;
674        }
675
676        // And now that we've got all our JS and TypeScript, actually write it
677        // out to the filesystem.
678        let extension = "js";
679
680        fn write<P, C>(path: P, contents: C) -> Result<(), anyhow::Error>
681        where
682            P: AsRef<Path>,
683            C: AsRef<[u8]>,
684        {
685            fs::write(&path, contents)
686                .with_context(|| format!("failed to write `{}`", path.as_ref().display()))
687        }
688
689        let js_path = out_dir.join(&self.stem).with_extension(extension);
690
691        if gen.mode.esm_integration() {
692            let js_name = format!("{}_bg.{}", self.stem, extension);
693
694            let start = gen.start.as_deref().unwrap_or("");
695
696            if matches!(gen.mode, OutputMode::Node { .. }) {
697                write(
698                    &js_path,
699                    format!(
700                        "\
701{start}
702export * from \"./{js_name}\";",
703                    ),
704                )?;
705            } else {
706                write(
707                    &js_path,
708                    format!(
709                        "\
710import * as wasm from \"./{wasm_name}.wasm\";
711export * from \"./{js_name}\";
712{start}"
713                    ),
714                )?;
715            }
716            write(out_dir.join(&js_name), reset_indentation(&gen.js))?;
717        } else {
718            write(&js_path, reset_indentation(&gen.js))?;
719        }
720
721        if gen.typescript {
722            let ts_path = js_path.with_extension("d.ts");
723            fs::write(&ts_path, &gen.ts)
724                .with_context(|| format!("failed to write `{}`", ts_path.display()))?;
725        }
726
727        if gen.typescript {
728            let ts_path = wasm_path.with_extension("wasm.d.ts");
729            let ts = wasm2es6js::typescript(&self.module)?;
730            fs::write(&ts_path, ts)
731                .with_context(|| format!("failed to write `{}`", ts_path.display()))?;
732        }
733
734        Ok(())
735    }
736}
737
738fn gc_module_and_adapters(module: &mut Module) {
739    loop {
740        // Fist up, cleanup the native Wasm module. Note that roots can come
741        // from custom sections, namely our Wasm interface types custom section
742        // as well as the aux section.
743        walrus::passes::gc::run(module);
744
745        // ... and afterwards we can delete any `implements` directives for any
746        // imports that have been deleted.
747        let imports_remaining = module
748            .imports
749            .iter()
750            .map(|i| i.id())
751            .collect::<HashSet<_>>();
752        let mut section = module
753            .customs
754            .delete_typed::<wit::NonstandardWitSection>()
755            .unwrap();
756        section
757            .implements
758            .retain(|pair| imports_remaining.contains(&pair.0));
759
760        // ... and after we delete the `implements` directive we try to
761        // delete some adapters themselves. If nothing is deleted, then we're
762        // good to go. If something is deleted though then we may have free'd up
763        // some functions in the main module to get deleted, so go again to gc
764        // things.
765        let aux = module.customs.get_typed::<wit::WasmBindgenAux>().unwrap();
766        let any_removed = section.gc(aux);
767        module.customs.add(*section);
768        if !any_removed {
769            break;
770        }
771    }
772}
773
774/// Returns a sorted iterator over a hash map, sorted based on key.
775///
776/// The intention of this API is to be used whenever the iteration order of a
777/// `HashMap` might affect the generated JS bindings. We want to ensure that the
778/// generated output is deterministic and we do so by ensuring that iteration of
779/// hash maps is consistently sorted.
780fn sorted_iter<K, V>(map: &HashMap<K, V>) -> impl Iterator<Item = (&K, &V)>
781where
782    K: Ord,
783{
784    let mut pairs = map.iter().collect::<Vec<_>>();
785    pairs.sort_by_key(|(k, _)| *k);
786    pairs.into_iter()
787}