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

fallow_mutation/
lib.rs
