fallow_mutation/
lib.rs

1//! Mutant site discovery and mutation-switching instrumentation.
2//!
3//! The crate is pure: it reads one source text and returns the mutants and
4//! the instrumented text. It does no IO, and it depends on no other Fallow
5//! workspace crate. The engine joins the mutants to graph, diff and
6//! complexity facts.
7//!
8//! The instrumented text is a splice over the original text. The crate never
9//! reprints the AST, so the output keeps the language of the input (TypeScript
10//! stays TypeScript, JSX stays JSX) and runner transforms see the original
11//! syntax.
12//!
13//! Subsumption is a static rule: negate-condition gives no mutant for a test
14//! that is a comparison or a logical expression, because the relational and
15//! logical operator mutants of that test cover it.
16
17mod blocks;
18mod collect;
19mod emit;
20mod id;
21mod operator;
22mod regex;
23
24use serde::Serialize;
25
26pub use blocks::{ScriptBlock, ScriptRole, instrument_blocks};
27pub use operator::Operator;
28
29/// The language of a source text.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
31#[serde(rename_all = "kebab-case")]
32pub enum SourceKind {
33    /// JavaScript. JSX syntax is accepted, and module or script mode is
34    /// detected from the content.
35    Js,
36    /// JavaScript with JSX.
37    Jsx,
38    /// TypeScript without JSX.
39    Ts,
40    /// TypeScript with JSX.
41    Tsx,
42}
43
44impl SourceKind {
45    /// Selects the kind from the file extension of `path`.
46    pub fn from_path(path: &str) -> Option<Self> {
47        let extension = path.rsplit_once('.')?.1;
48        match extension {
49            "js" | "mjs" | "cjs" => Some(Self::Js),
50            "jsx" => Some(Self::Jsx),
51            "ts" | "mts" | "cts" => Some(Self::Ts),
52            "tsx" => Some(Self::Tsx),
53            _ => None,
54        }
55    }
56
57    /// The Oxc source type for this kind.
58    pub const fn source_type(self) -> oxc_span::SourceType {
59        match self {
60            Self::Js => oxc_span::SourceType::unambiguous().with_jsx(true),
61            Self::Jsx => oxc_span::SourceType::jsx(),
62            Self::Ts => oxc_span::SourceType::ts(),
63            Self::Tsx => oxc_span::SourceType::tsx(),
64        }
65    }
66}
67
68/// Options for [`instrument`].
69#[derive(Debug, Clone, PartialEq, Eq)]
70pub struct MutationOptions {
71    /// The operators that may produce mutants.
72    pub operators: Vec<Operator>,
73    /// Byte ranges in the original text. When set, a mutant is kept only when
74    /// its span overlaps one of the ranges. `None` mutates the whole file.
75    pub ranges: Option<Vec<(u32, u32)>>,
76}
77
78impl Default for MutationOptions {
79    fn default() -> Self {
80        Self {
81            operators: Operator::ALL.to_vec(),
82            ranges: None,
83        }
84    }
85}
86
87/// The stable identity of a mutant: 16 lowercase hex digits.
88#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
89#[serde(transparent)]
90pub struct MutantId(pub String);
91
92impl MutantId {
93    /// The id as text.
94    pub fn as_str(&self) -> &str {
95        &self.0
96    }
97}
98
99impl std::fmt::Display for MutantId {
100    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
101        f.write_str(&self.0)
102    }
103}
104
105/// The function that contains a mutant.
106#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
107pub struct FunctionRef {
108    /// The function name, when the syntax gives one.
109    pub name: Option<String>,
110    /// The original byte span of the function.
111    pub span: (u32, u32),
112}
113
114/// One mutant.
115#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
116pub struct Mutant {
117    /// The stable id.
118    pub id: MutantId,
119    /// The operator that produced the mutant.
120    pub operator: Operator,
121    /// The original byte span that the mutant replaces.
122    pub span: (u32, u32),
123    /// The 1-based line of the span start.
124    pub line: u32,
125    /// The 0-based byte column of the span start.
126    pub column: u32,
127    /// The original text of the span.
128    pub original: String,
129    /// The text that replaces the span. The original source with this
130    /// replacement applied is the mutated program. At the start of an
131    /// expression statement, the text can start with `void`, so that the
132    /// statement does not join the line before it.
133    pub replacement: String,
134    /// The innermost function that contains the mutant.
135    pub enclosing_function: Option<FunctionRef>,
136}
137
138/// One copied run of original text in the instrumented output.
139#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
140pub struct SpliceSegment {
141    /// The byte offset in the instrumented output.
142    pub generated_start: u32,
143    /// The byte offset in the original text.
144    pub original_start: u32,
145    /// The length in bytes.
146    pub len: u32,
147}
148
149/// Maps instrumented byte offsets back to original byte offsets.
150///
151/// Each segment is a run of original text that the output copies unchanged.
152/// Text that the instrumentation adds has no segment. The segments are in
153/// increasing `generated_start` order.
154#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize)]
155pub struct SpliceMap {
156    /// The copied runs, in output order.
157    pub segments: Vec<SpliceSegment>,
158}
159
160impl SpliceMap {
161    /// The original offset of a generated offset, or `None` when the
162    /// instrumentation added the byte.
163    pub fn original_offset(&self, generated: u32) -> Option<u32> {
164        let index = self
165            .segments
166            .partition_point(|segment| segment.generated_start <= generated);
167        let segment = self.segments.get(index.checked_sub(1)?)?;
168        let delta = generated - segment.generated_start;
169        (delta < segment.len).then_some(segment.original_start + delta)
170    }
171}
172
173/// The result of [`instrument`].
174#[derive(Debug, Clone, PartialEq, Eq)]
175pub struct Instrumented {
176    /// The mutants, in source order.
177    pub mutants: Vec<Mutant>,
178    /// The instrumented source text.
179    pub code: String,
180    /// The map from output offsets to original offsets.
181    pub map: SpliceMap,
182}
183
184/// An error from [`instrument`].
185#[derive(Debug, Clone, PartialEq, Eq)]
186pub enum MutationError {
187    /// The source text does not parse.
188    Parse {
189        /// The parser messages.
190        messages: Vec<String>,
191    },
192    /// The source text or the instrumented text is larger than `u32::MAX`
193    /// bytes.
194    TooLarge,
195    /// The source declares a binding with a name that the prelude uses. See
196    /// [`RESERVED_PREFIX`].
197    ReservedName {
198        /// The declared name.
199        name: String,
200    },
201}
202
203impl std::fmt::Display for MutationError {
204    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
205        match self {
206            Self::Parse { messages } => {
207                write!(f, "the source does not parse: {}", messages.join("; "))
208            }
209            Self::TooLarge => {
210                f.write_str("the source or the instrumented output is larger than 4 GiB")
211            }
212            Self::ReservedName { name } => write!(
213                f,
214                "the source declares `{name}`, a name that the mutation prelude reserves"
215            ),
216        }
217    }
218}
219
220impl std::error::Error for MutationError {}
221
222/// True for a byte that can continue an identifier. Non-ASCII bytes count,
223/// so that an edit never joins a Unicode identifier with a keyword.
224const fn is_identifier_byte(byte: u8) -> bool {
225    byte.is_ascii_alphanumeric() || matches!(byte, b'_' | b'$') || byte >= 0x80
226}
227
228/// The name prefix that the instrumentation reserves.
229///
230/// The prelude declares [`ACTIVE_FUNCTION`] and [`HIT_FUNCTION`] at the top
231/// level of each instrumented file. A source that declares a binding with one
232/// of these two names, at any scope, gives [`MutationError::ReservedName`],
233/// because that binding would replace or shadow the prelude function. Other
234/// names with this prefix do not give an error now. Do not use names with
235/// this prefix in project code, because a later prelude can use them.
236pub const RESERVED_PREFIX: &str = "__fallow_m_";
237
238/// The prelude function that asks the runtime whether a mutant is active.
239///
240/// The instrumented output calls `__fallow_m_a(id)` before each mutated
241/// branch. The function returns `globalThis.__fallowMutation.a(id)`, or
242/// `false` when the runtime object is not set.
243pub const ACTIVE_FUNCTION: &str = "__fallow_m_a";
244
245/// The prelude function that reports a hit on the original branch.
246///
247/// The instrumented output calls `__fallow_m_c(id)` for each mutant of a site
248/// before the original branch runs. The function calls
249/// `globalThis.__fallowMutation.c(id)` when the runtime object is set.
250pub const HIT_FUNCTION: &str = "__fallow_m_c";
251
252/// Finds the mutants in `source` and returns the instrumented text.
253///
254/// `path` is part of each mutant id. Use the project-relative path, so that
255/// ids are the same on each machine.
256pub fn instrument(
257    source: &str,
258    path: &str,
259    source_type: SourceKind,
260    options: &MutationOptions,
261) -> Result<Instrumented, MutationError> {
262    let mut seen_ids = std::collections::BTreeSet::new();
263    let text = TextInput {
264        source,
265        path,
266        kind: source_type,
267        role: None,
268        prelude: true,
269    };
270    instrument_text(&text, options, &mut seen_ids)
271}
272
273/// One source text for [`instrument_text`]: a whole file or one script block.
274pub(crate) struct TextInput<'s> {
275    pub(crate) source: &'s str,
276    pub(crate) path: &'s str,
277    pub(crate) kind: SourceKind,
278    /// The role of a script block, or `None` for a whole file.
279    pub(crate) role: Option<ScriptRole>,
280    /// True when the text gets the prelude.
281    pub(crate) prelude: bool,
282}
283
284/// Instruments one text. The spans, lines and columns of the result are
285/// relative to the text. `seen_ids` holds the ids of earlier texts of the
286/// same file, so that each id stays unique in the file.
287pub(crate) fn instrument_text(
288    input: &TextInput<'_>,
289    options: &MutationOptions,
290    seen_ids: &mut std::collections::BTreeSet<MutantId>,
291) -> Result<Instrumented, MutationError> {
292    let source = input.source;
293    if u32::try_from(source.len()).is_err() {
294        return Err(MutationError::TooLarge);
295    }
296    let allocator = oxc_allocator::Allocator::default();
297    let parsed = oxc_parser::Parser::new(&allocator, source, input.kind.source_type()).parse();
298    if parsed.fatal_error || parsed.diagnostics.has_errors() {
299        let messages = parsed.diagnostics.iter().map(ToString::to_string).collect();
300        return Err(MutationError::Parse { messages });
301    }
302    if let Some(name) = reserved_binding(&parsed.program) {
303        return Err(MutationError::ReservedName { name });
304    }
305    let collected = collect::collect(&parsed.program, source);
306    let protected = input
307        .role
308        .map(|role| blocks::protected_spans(&parsed.program, role))
309        .unwrap_or_default();
310    let insertions = header_insertions(&parsed.program, source, input.prelude);
311    let line_starts = line_starts(source);
312
313    let mut mutants = Vec::new();
314    let mut emit_sites = Vec::new();
315    for site in collected.sites {
316        if protected.excludes(site.span) {
317            continue;
318        }
319        let kept = select_candidates(source, &site, &collected.statement_starts, options);
320        if kept.is_empty() {
321            continue;
322        }
323        let mut emit_mutants = Vec::with_capacity(kept.len());
324        for candidate in kept {
325            let id = unique_id(input.path, source, &site, &candidate, seen_ids);
326            let (line, column) = line_column(&line_starts, candidate.region.0);
327            emit_mutants.push(emit::EmitMutant {
328                id: id.0.clone(),
329                region: candidate.region,
330                replacement: candidate.replacement.clone(),
331            });
332            mutants.push(Mutant {
333                id,
334                operator: candidate.operator,
335                span: candidate.region,
336                line,
337                column,
338                original: slice(source, candidate.region).to_owned(),
339                replacement: candidate.replacement,
340                enclosing_function: site.function.clone(),
341            });
342        }
343        emit_sites.push(emit::EmitSite {
344            span: site.span,
345            mutants: emit_mutants,
346        });
347    }
348    mutants.sort_by_key(|mutant| mutant.span);
349    let (code, map) = emit::emit(
350        source,
351        &emit_sites,
352        &collected.statement_starts,
353        &insertions,
354    );
355    // The splice map holds `u32` offsets. When the output fits, no offset
356    // was truncated.
357    if u32::try_from(code.len()).is_err() {
358        return Err(MutationError::TooLarge);
359    }
360    Ok(Instrumented { mutants, code, map })
361}
362
363/// The first binding in `program` with the name of a prelude function.
364fn reserved_binding(program: &oxc_ast::ast::Program<'_>) -> Option<String> {
365    use oxc_ast_visit::Visit;
366
367    #[derive(Default)]
368    struct Finder {
369        found: Option<String>,
370    }
371    impl<'a> Visit<'a> for Finder {
372        fn visit_binding_identifier(&mut self, it: &oxc_ast::ast::BindingIdentifier<'a>) {
373            let name = it.name.as_str();
374            if self.found.is_none() && (name == ACTIVE_FUNCTION || name == HIT_FUNCTION) {
375                self.found = Some(name.to_owned());
376            }
377        }
378    }
379
380    let mut finder = Finder::default();
381    finder.visit_program(program);
382    finder.found
383}
384
385/// The prelude: two function declarations that call the runtime.
386///
387/// The prelude uses hoisted function declarations, not a `const`. In a module
388/// cycle, another module can call a hoisted function of this module before
389/// the prelude line runs. A `const` binding is then in its temporal dead
390/// zone and throws a `ReferenceError`. A function declaration exists from
391/// the start of the module, and each call reads the runtime object again.
392/// Two classic scripts can also declare the same functions without a
393/// redeclaration error.
394const PRELUDE: &str = "function __fallow_m_a(id) { const m = globalThis.__fallowMutation; return m ? m.a(id) : false; } function __fallow_m_c(id) { const m = globalThis.__fallowMutation; if (m) m.c(id); }";
395
396const TS_NOCHECK: &str = "// @ts-nocheck";
397
398/// The `// @ts-nocheck` comment goes after the hashbang and the leading
399/// comments, so that pragmas such as `@jsxImportSource` stay before the first
400/// token. The prelude goes after the directive prologue, so that
401/// `"use strict"` and `"use client"` stay the first statements.
402///
403/// A directive can share a line with the last leading comment. The line
404/// comment then ends with a newline, or the directive and the prelude become
405/// comment text.
406///
407/// A script block without the prelude gets only the comment.
408fn header_insertions(
409    program: &oxc_ast::ast::Program<'_>,
410    source: &str,
411    prelude: bool,
412) -> Vec<emit::Insertion> {
413    let offset = leading_end(program, source);
414    let line_break_follows = source
415        .get(offset as usize..)
416        .is_some_and(|rest| rest.starts_with(['\n', '\r', '\u{2028}', '\u{2029}']));
417    let nocheck = if offset == 0 {
418        format!("{TS_NOCHECK}\n")
419    } else if program.directives.is_empty() || line_break_follows {
420        format!("\n{TS_NOCHECK}")
421    } else {
422        format!("\n{TS_NOCHECK}\n")
423    };
424    if !prelude {
425        return vec![emit::Insertion {
426            offset,
427            text: nocheck,
428        }];
429    }
430    let Some(last) = program.directives.last() else {
431        let text = if offset == 0 {
432            format!("{nocheck}{PRELUDE}\n")
433        } else {
434            format!("{nocheck}\n{PRELUDE}")
435        };
436        return vec![emit::Insertion { offset, text }];
437    };
438    let end = last.span.end;
439    let terminated = source
440        .get(..end as usize)
441        .is_some_and(|text| text.ends_with(';'));
442    let separator = if terminated { "" } else { ";" };
443    vec![
444        emit::Insertion {
445            offset,
446            text: nocheck,
447        },
448        emit::Insertion {
449            offset: end,
450            text: format!("{separator}{PRELUDE}"),
451        },
452    ]
453}
454
455/// The end of the hashbang and of the comments before the first token.
456fn leading_end(program: &oxc_ast::ast::Program<'_>, source: &str) -> u32 {
457    use oxc_span::GetSpan;
458    let first_token = program
459        .directives
460        .first()
461        .map(|directive| directive.span.start)
462        .or_else(|| program.body.first().map(|statement| statement.span().start))
463        .unwrap_or(source.len() as u32);
464    let hashbang_end = program
465        .hashbang
466        .as_ref()
467        .map_or(0, |hashbang| hashbang.span.end);
468    program
469        .comments
470        .iter()
471        .take_while(|comment| comment.span.end <= first_token)
472        .map(|comment| comment.span.end)
473        .last()
474        .map_or(hashbang_end, |end| end.max(hashbang_end))
475}
476
477fn slice(source: &str, span: (u32, u32)) -> &str {
478    source
479        .get(span.0 as usize..span.1 as usize)
480        .unwrap_or_default()
481}
482
483/// Applies the operator and range options, then drops candidates that give
484/// the original text or the same text as an earlier candidate of the site.
485fn select_candidates(
486    source: &str,
487    site: &collect::Site,
488    statement_starts: &std::collections::BTreeSet<u32>,
489    options: &MutationOptions,
490) -> Vec<collect::Candidate> {
491    let original = slice(source, site.span);
492    let mut texts = std::collections::BTreeSet::new();
493    let mut kept = Vec::new();
494    for candidate in &site.candidates {
495        if !options.operators.contains(&candidate.operator) {
496            continue;
497        }
498        let (start, end) = candidate.region;
499        let in_range = options
500            .ranges
501            .as_ref()
502            .is_none_or(|ranges| ranges.iter().any(|&(from, to)| start < to && from < end));
503        if !in_range {
504            continue;
505        }
506        let replacement = guard_statement_start(source, statement_starts, candidate);
507        let mutated = format!(
508            "{}{}{}",
509            slice(source, (site.span.0, start)),
510            replacement,
511            slice(source, (end, site.span.1)),
512        );
513        if mutated == original || !texts.insert(mutated) {
514            continue;
515        }
516        kept.push(collect::Candidate {
517            operator: candidate.operator,
518            region: candidate.region,
519            replacement,
520        });
521    }
522    kept
523}
524
525/// Characters that continue the previous line when a statement starts with
526/// them and that line has no semicolon.
527const ASI_HAZARDS: [char; 6] = ['(', '[', '`', '+', '-', '/'];
528
529/// True when a statement that starts with `text` can join the line before it.
530/// A prefix `++` or `--` cannot, because the postfix forms forbid a line
531/// break before the operator.
532fn starts_with_asi_hazard(text: &str) -> bool {
533    let hazard = text.starts_with(ASI_HAZARDS);
534    hazard && !text.starts_with("++") && !text.starts_with("--")
535}
536
537/// Prefixes `void` to a replacement that starts an expression statement with
538/// an ASI hazard, so that the original source with the replacement applied
539/// keeps the statement boundary. When the original also starts with a hazard,
540/// the line before it already ends the statement, and no prefix is needed.
541fn guard_statement_start(
542    source: &str,
543    statement_starts: &std::collections::BTreeSet<u32>,
544    candidate: &collect::Candidate,
545) -> String {
546    let (start, end) = candidate.region;
547    let guarded = statement_starts.contains(&start)
548        && starts_with_asi_hazard(&candidate.replacement)
549        && !starts_with_asi_hazard(slice(source, (start, end)));
550    if !guarded {
551        return candidate.replacement.clone();
552    }
553    // `do!f()` has no space after the keyword; `dovoid` would be a name.
554    let joins = source
555        .as_bytes()
556        .get((start as usize).wrapping_sub(1))
557        .is_some_and(|&byte| is_identifier_byte(byte));
558    let prefix = if joins { " void " } else { "void " };
559    format!("{prefix}{}", candidate.replacement)
560}
561
562fn unique_id(
563    path: &str,
564    source: &str,
565    site: &collect::Site,
566    candidate: &collect::Candidate,
567    seen: &mut std::collections::BTreeSet<MutantId>,
568) -> MutantId {
569    let anchor_start = site.anchor.0;
570    let input = id::IdInput {
571        path,
572        anchor_text: slice(source, site.anchor),
573        relative: (
574            candidate.region.0.saturating_sub(anchor_start),
575            candidate.region.1.saturating_sub(anchor_start),
576        ),
577        operator: candidate.operator,
578        replacement: &candidate.replacement,
579    };
580    let mut occurrence = 0;
581    loop {
582        let id = id::mutant_id(&input, occurrence);
583        if seen.insert(id.clone()) {
584            return id;
585        }
586        occurrence += 1;
587    }
588}
589
590fn line_starts(source: &str) -> Vec<u32> {
591    std::iter::once(0)
592        .chain(
593            source
594                .match_indices('\n')
595                .map(|(index, _)| index as u32 + 1),
596        )
597        .collect()
598}
599
600fn line_column(line_starts: &[u32], offset: u32) -> (u32, u32) {
601    let index = line_starts
602        .partition_point(|&start| start <= offset)
603        .saturating_sub(1);
604    let start = line_starts.get(index).copied().unwrap_or(0);
605    (index as u32 + 1, offset - start)
606}
fallow_mutation/lib.rs

fallow_mutation/
lib.rs
