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

fallow_mutation/
lib.rs
