fix(coverage): merge coverage ranges (#13334)

Covered ranges were not merged and thus it appeared that some lines
might be uncovered. To fix this I used "v8-coverage" that takes care
of merging the ranges properly. With this change, coverage collected
from a file by multiple entrypoints is now correctly calculated.

I ended up forking https://github.com/demurgos/v8-coverage and adding
"cli/tools/coverage/merge.rs" and "cli/tools/coverage/range_tree.rs".

1 files changed, 0 insertions, 714 deletions

diff --git a/cli/tools/coverage.rs b/cli/tools/coverage.rs
deleted file mode 100644
index 3cec35606..000000000
--- a/cli/tools/coverage.rs
+++ /dev/null
@@ -1,714 +0,0 @@
-// Copyright 2018-2022 the Deno authors. All rights reserved. MIT license.
-
-use crate::colors;
-use crate::flags::CoverageFlags;
-use crate::flags::Flags;
-use crate::fs_util::collect_files;
-use crate::proc_state::ProcState;
-use crate::source_maps::SourceMapGetter;
-use crate::tools::fmt::format_json;
-
-use deno_ast::MediaType;
-use deno_ast::ModuleSpecifier;
-use deno_core::anyhow::anyhow;
-use deno_core::anyhow::Context;
-use deno_core::error::AnyError;
-use deno_core::serde_json;
-use deno_core::url::Url;
-use deno_core::LocalInspectorSession;
-use regex::Regex;
-use serde::Deserialize;
-use serde::Serialize;
-use sourcemap::SourceMap;
-use std::fs;
-use std::fs::File;
-use std::io::BufWriter;
-use std::io::Write;
-use std::path::PathBuf;
-use text_lines::TextLines;
-use uuid::Uuid;
-
-#[derive(Debug, Serialize, Deserialize, Clone)]
-#[serde(rename_all = "camelCase")]
-struct CoverageRange {
-  /// Start byte index.
-  start_offset: usize,
-  /// End byte index.
-  end_offset: usize,
-  count: usize,
-}
-
-#[derive(Debug, Serialize, Deserialize, Clone)]
-#[serde(rename_all = "camelCase")]
-struct FunctionCoverage {
-  function_name: String,
-  ranges: Vec<CoverageRange>,
-  is_block_coverage: bool,
-}
-
-#[derive(Debug, Serialize, Deserialize, Clone)]
-#[serde(rename_all = "camelCase")]
-struct ScriptCoverage {
-  script_id: String,
-  url: String,
-  functions: Vec<FunctionCoverage>,
-}
-
-#[derive(Debug, Serialize, Deserialize)]
-#[serde(rename_all = "camelCase")]
-struct StartPreciseCoverageParameters {
-  call_count: bool,
-  detailed: bool,
-  allow_triggered_updates: bool,
-}
-
-#[derive(Debug, Serialize, Deserialize)]
-#[serde(rename_all = "camelCase")]
-struct StartPreciseCoverageReturnObject {
-  timestamp: f64,
-}
-
-#[derive(Debug, Serialize, Deserialize)]
-#[serde(rename_all = "camelCase")]
-struct TakePreciseCoverageReturnObject {
-  result: Vec<ScriptCoverage>,
-  timestamp: f64,
-}
-
-pub struct CoverageCollector {
-  pub dir: PathBuf,
-  session: LocalInspectorSession,
-}
-
-impl CoverageCollector {
-  pub fn new(dir: PathBuf, session: LocalInspectorSession) -> Self {
-    Self { dir, session }
-  }
-
-  async fn enable_debugger(&mut self) -> Result<(), AnyError> {
-    self.session.post_message("Debugger.enable", None).await?;
-    Ok(())
-  }
-
-  async fn enable_profiler(&mut self) -> Result<(), AnyError> {
-    self.session.post_message("Profiler.enable", None).await?;
-    Ok(())
-  }
-
-  async fn disable_debugger(&mut self) -> Result<(), AnyError> {
-    self.session.post_message("Debugger.disable", None).await?;
-    Ok(())
-  }
-
-  async fn disable_profiler(&mut self) -> Result<(), AnyError> {
-    self.session.post_message("Profiler.disable", None).await?;
-    Ok(())
-  }
-
-  async fn start_precise_coverage(
-    &mut self,
-    parameters: StartPreciseCoverageParameters,
-  ) -> Result<StartPreciseCoverageReturnObject, AnyError> {
-    let parameters_value = serde_json::to_value(parameters)?;
-    let return_value = self
-      .session
-      .post_message("Profiler.startPreciseCoverage", Some(parameters_value))
-      .await?;
-
-    let return_object = serde_json::from_value(return_value)?;
-
-    Ok(return_object)
-  }
-
-  async fn take_precise_coverage(
-    &mut self,
-  ) -> Result<TakePreciseCoverageReturnObject, AnyError> {
-    let return_value = self
-      .session
-      .post_message("Profiler.takePreciseCoverage", None)
-      .await?;
-
-    let return_object = serde_json::from_value(return_value)?;
-
-    Ok(return_object)
-  }
-
-  pub async fn start_collecting(&mut self) -> Result<(), AnyError> {
-    self.enable_debugger().await?;
-    self.enable_profiler().await?;
-    self
-      .start_precise_coverage(StartPreciseCoverageParameters {
-        call_count: true,
-        detailed: true,
-        allow_triggered_updates: false,
-      })
-      .await?;
-
-    Ok(())
-  }
-
-  pub async fn stop_collecting(&mut self) -> Result<(), AnyError> {
-    fs::create_dir_all(&self.dir)?;
-
-    let script_coverages = self.take_precise_coverage().await?.result;
-    for script_coverage in script_coverages {
-      let filename = format!("{}.json", Uuid::new_v4());
-      let filepath = self.dir.join(filename);
-
-      let mut out = BufWriter::new(File::create(filepath)?);
-      let coverage = serde_json::to_string(&script_coverage)?;
-      let formated_coverage =
-        format_json(&coverage, &Default::default()).unwrap_or(coverage);
-
-      out.write_all(formated_coverage.as_bytes())?;
-      out.flush()?;
-    }
-
-    self.disable_debugger().await?;
-    self.disable_profiler().await?;
-
-    Ok(())
-  }
-}
-
-struct BranchCoverageItem {
-  line_index: usize,
-  block_number: usize,
-  branch_number: usize,
-  taken: Option<usize>,
-  is_hit: bool,
-}
-
-struct FunctionCoverageItem {
-  name: String,
-  line_index: usize,
-  execution_count: usize,
-}
-
-struct CoverageReport {
-  url: ModuleSpecifier,
-  named_functions: Vec<FunctionCoverageItem>,
-  branches: Vec<BranchCoverageItem>,
-  found_lines: Vec<(usize, usize)>,
-}
-
-fn generate_coverage_report(
-  script_coverage: &ScriptCoverage,
-  script_source: &str,
-  maybe_source_map: &Option<Vec<u8>>,
-) -> CoverageReport {
-  let maybe_source_map = maybe_source_map
-    .as_ref()
-    .map(|source_map| SourceMap::from_slice(source_map).unwrap());
-  let text_lines = TextLines::new(script_source);
-
-  let comment_spans = deno_ast::lex(script_source, MediaType::JavaScript)
-    .into_iter()
-    .filter(|item| {
-      matches!(item.inner, deno_ast::TokenOrComment::Comment { .. })
-    })
-    .map(|item| item.span)
-    .collect::<Vec<_>>();
-
-  let url = Url::parse(&script_coverage.url).unwrap();
-  let mut coverage_report = CoverageReport {
-    url,
-    named_functions: Vec::with_capacity(
-      script_coverage
-        .functions
-        .iter()
-        .filter(|f| !f.function_name.is_empty())
-        .count(),
-    ),
-    branches: Vec::new(),
-    found_lines: Vec::new(),
-  };
-
-  for function in &script_coverage.functions {
-    if function.function_name.is_empty() {
-      continue;
-    }
-
-    let source_line_index =
-      text_lines.line_index(function.ranges[0].start_offset);
-    let line_index = if let Some(source_map) = maybe_source_map.as_ref() {
-      source_map
-        .tokens()
-        .find(|token| token.get_dst_line() as usize == source_line_index)
-        .map(|token| token.get_src_line() as usize)
-        .unwrap_or(0)
-    } else {
-      source_line_index
-    };
-
-    coverage_report.named_functions.push(FunctionCoverageItem {
-      name: function.function_name.clone(),
-      line_index,
-      execution_count: function.ranges[0].count,
-    });
-  }
-
-  for (block_number, function) in script_coverage.functions.iter().enumerate() {
-    let block_hits = function.ranges[0].count;
-    for (branch_number, range) in function.ranges[1..].iter().enumerate() {
-      let source_line_index = text_lines.line_index(range.start_offset);
-      let line_index = if let Some(source_map) = maybe_source_map.as_ref() {
-        source_map
-          .tokens()
-          .find(|token| token.get_dst_line() as usize == source_line_index)
-          .map(|token| token.get_src_line() as usize)
-          .unwrap_or(0)
-      } else {
-        source_line_index
-      };
-
-      // From https://manpages.debian.org/unstable/lcov/geninfo.1.en.html:
-      //
-      // Block number and branch number are gcc internal IDs for the branch. Taken is either '-'
-      // if the basic block containing the branch was never executed or a number indicating how
-      // often that branch was taken.
-      //
-      // However with the data we get from v8 coverage profiles it seems we can't actually hit
-      // this as appears it won't consider any nested branches it hasn't seen but its here for
-      // the sake of accuracy.
-      let taken = if block_hits > 0 {
-        Some(range.count)
-      } else {
-        None
-      };
-
-      coverage_report.branches.push(BranchCoverageItem {
-        line_index,
-        block_number,
-        branch_number,
-        taken,
-        is_hit: range.count > 0,
-      })
-    }
-  }
-
-  // TODO(caspervonb): collect uncovered ranges on the lines so that we can highlight specific
-  // parts of a line in color (word diff style) instead of the entire line.
-  let mut line_counts = Vec::with_capacity(text_lines.lines_count());
-  for line_index in 0..text_lines.lines_count() {
-    let line_start_offset = text_lines.line_start(line_index);
-    let line_end_offset = text_lines.line_end(line_index);
-    let ignore = comment_spans.iter().any(|span| {
-      (span.lo.0 as usize) <= line_start_offset
-        && (span.hi.0 as usize) >= line_end_offset
-    }) || script_source[line_start_offset..line_end_offset]
-      .trim()
-      .is_empty();
-    let mut count = 0;
-
-    if ignore {
-      count = 1;
-    } else {
-      // Count the hits of ranges that include the entire line which will always be at-least one
-      // as long as the code has been evaluated.
-      for function in &script_coverage.functions {
-        for range in &function.ranges {
-          if range.start_offset <= line_start_offset
-            && range.end_offset >= line_end_offset
-          {
-            count += range.count;
-          }
-        }
-      }
-
-      // We reset the count if any block with a zero count overlaps with the line range.
-      for function in &script_coverage.functions {
-        for range in &function.ranges {
-          if range.count > 0 {
-            continue;
-          }
-
-          let overlaps = range.start_offset < line_end_offset
-            && range.end_offset > line_start_offset;
-          if overlaps {
-            count = 0;
-          }
-        }
-      }
-    }
-
-    line_counts.push(count);
-  }
-
-  coverage_report.found_lines =
-    if let Some(source_map) = maybe_source_map.as_ref() {
-      let mut found_lines = line_counts
-        .iter()
-        .enumerate()
-        .map(|(index, count)| {
-          // get all the mappings from this destination line to a different src line
-          let mut results = source_map
-            .tokens()
-            .filter(move |token| token.get_dst_line() as usize == index)
-            .map(move |token| (token.get_src_line() as usize, *count))
-            .collect::<Vec<_>>();
-          // only keep the results that point at different src lines
-          results.sort_unstable_by_key(|(index, _)| *index);
-          results.dedup_by_key(|(index, _)| *index);
-          results.into_iter()
-        })
-        .flatten()
-        .collect::<Vec<(usize, usize)>>();
-
-      found_lines.sort_unstable_by_key(|(index, _)| *index);
-      // combine duplicated lines
-      for i in (1..found_lines.len()).rev() {
-        if found_lines[i].0 == found_lines[i - 1].0 {
-          found_lines[i - 1].1 += found_lines[i].1;
-          found_lines.remove(i);
-        }
-      }
-      found_lines
-    } else {
-      line_counts
-        .into_iter()
-        .enumerate()
-        .map(|(index, count)| (index, count))
-        .collect::<Vec<(usize, usize)>>()
-    };
-
-  coverage_report
-}
-
-enum CoverageReporterKind {
-  Pretty,
-  Lcov,
-}
-
-fn create_reporter(
-  kind: CoverageReporterKind,
-) -> Box<dyn CoverageReporter + Send> {
-  match kind {
-    CoverageReporterKind::Lcov => Box::new(LcovCoverageReporter::new()),
-    CoverageReporterKind::Pretty => Box::new(PrettyCoverageReporter::new()),
-  }
-}
-
-trait CoverageReporter {
-  fn report(&mut self, coverage_report: &CoverageReport, file_text: &str);
-
-  fn done(&mut self);
-}
-
-struct LcovCoverageReporter {}
-
-impl LcovCoverageReporter {
-  pub fn new() -> LcovCoverageReporter {
-    LcovCoverageReporter {}
-  }
-}
-
-impl CoverageReporter for LcovCoverageReporter {
-  fn report(&mut self, coverage_report: &CoverageReport, _file_text: &str) {
-    let file_path = coverage_report
-      .url
-      .to_file_path()
-      .ok()
-      .map(|p| p.to_str().map(|p| p.to_string()))
-      .flatten()
-      .unwrap_or_else(|| coverage_report.url.to_string());
-    println!("SF:{}", file_path);
-
-    for function in &coverage_report.named_functions {
-      println!("FN:{},{}", function.line_index + 1, function.name);
-    }
-
-    for function in &coverage_report.named_functions {
-      println!("FNDA:{},{}", function.execution_count, function.name);
-    }
-
-    let functions_found = coverage_report.named_functions.len();
-    println!("FNF:{}", functions_found);
-    let functions_hit = coverage_report
-      .named_functions
-      .iter()
-      .filter(|f| f.execution_count > 0)
-      .count();
-    println!("FNH:{}", functions_hit);
-
-    for branch in &coverage_report.branches {
-      let taken = if let Some(taken) = &branch.taken {
-        taken.to_string()
-      } else {
-        "-".to_string()
-      };
-
-      println!(
-        "BRDA:{},{},{},{}",
-        branch.line_index + 1,
-        branch.block_number,
-        branch.branch_number,
-        taken
-      );
-    }
-
-    let branches_found = coverage_report.branches.len();
-    println!("BRF:{}", branches_found);
-    let branches_hit =
-      coverage_report.branches.iter().filter(|b| b.is_hit).count();
-    println!("BRH:{}", branches_hit);
-
-    for (index, count) in &coverage_report.found_lines {
-      println!("DA:{},{}", index + 1, count);
-    }
-
-    let lines_hit = coverage_report
-      .found_lines
-      .iter()
-      .filter(|(_, count)| *count != 0)
-      .count();
-    println!("LH:{}", lines_hit);
-
-    let lines_found = coverage_report.found_lines.len();
-    println!("LF:{}", lines_found);
-
-    println!("end_of_record");
-  }
-
-  fn done(&mut self) {}
-}
-
-struct PrettyCoverageReporter {}
-
-impl PrettyCoverageReporter {
-  pub fn new() -> PrettyCoverageReporter {
-    PrettyCoverageReporter {}
-  }
-}
-
-impl CoverageReporter for PrettyCoverageReporter {
-  fn report(&mut self, coverage_report: &CoverageReport, file_text: &str) {
-    let lines = file_text.split('\n').collect::<Vec<_>>();
-    print!("cover {} ... ", coverage_report.url);
-
-    let hit_lines = coverage_report
-      .found_lines
-      .iter()
-      .filter(|(_, count)| *count > 0)
-      .map(|(index, _)| *index);
-
-    let missed_lines = coverage_report
-      .found_lines
-      .iter()
-      .filter(|(_, count)| *count == 0)
-      .map(|(index, _)| *index);
-
-    let lines_found = coverage_report.found_lines.len();
-    let lines_hit = hit_lines.count();
-    let line_ratio = lines_hit as f32 / lines_found as f32;
-
-    let line_coverage =
-      format!("{:.3}% ({}/{})", line_ratio * 100.0, lines_hit, lines_found);
-
-    if line_ratio >= 0.9 {
-      println!("{}", colors::green(&line_coverage));
-    } else if line_ratio >= 0.75 {
-      println!("{}", colors::yellow(&line_coverage));
-    } else {
-      println!("{}", colors::red(&line_coverage));
-    }
-
-    let mut last_line = None;
-    for line_index in missed_lines {
-      const WIDTH: usize = 4;
-      const SEPERATOR: &str = "|";
-
-      // Put a horizontal separator between disjoint runs of lines
-      if let Some(last_line) = last_line {
-        if last_line + 1 != line_index {
-          let dash = colors::gray("-".repeat(WIDTH + 1));
-          println!("{}{}{}", dash, colors::gray(SEPERATOR), dash);
-        }
-      }
-
-      println!(
-        "{:width$} {} {}",
-        line_index + 1,
-        colors::gray(SEPERATOR),
-        colors::red(&lines[line_index]),
-        width = WIDTH
-      );
-
-      last_line = Some(line_index);
-    }
-  }
-
-  fn done(&mut self) {}
-}
-
-fn collect_coverages(
-  files: Vec<PathBuf>,
-  ignore: Vec<PathBuf>,
-) -> Result<Vec<ScriptCoverage>, AnyError> {
-  let mut coverages: Vec<ScriptCoverage> = Vec::new();
-  let file_paths = collect_files(&files, &ignore, |file_path| {
-    file_path.extension().map_or(false, |ext| ext == "json")
-  })?;
-
-  for file_path in file_paths {
-    let json = fs::read_to_string(file_path.as_path())?;
-    let new_coverage: ScriptCoverage = serde_json::from_str(&json)?;
-
-    let existing_coverage =
-      coverages.iter_mut().find(|x| x.url == new_coverage.url);
-
-    if let Some(existing_coverage) = existing_coverage {
-      for new_function in new_coverage.functions {
-        let existing_function = existing_coverage
-          .functions
-          .iter_mut()
-          .find(|x| x.function_name == new_function.function_name);
-
-        if let Some(existing_function) = existing_function {
-          for new_range in new_function.ranges {
-            let existing_range =
-              existing_function.ranges.iter_mut().find(|x| {
-                x.start_offset == new_range.start_offset
-                  && x.end_offset == new_range.end_offset
-              });
-
-            if let Some(existing_range) = existing_range {
-              existing_range.count += new_range.count;
-            } else {
-              existing_function.ranges.push(new_range);
-            }
-          }
-        } else {
-          existing_coverage.functions.push(new_function);
-        }
-      }
-    } else {
-      coverages.push(new_coverage);
-    }
-  }
-
-  coverages.sort_by_key(|k| k.url.clone());
-
-  Ok(coverages)
-}
-
-fn filter_coverages(
-  coverages: Vec<ScriptCoverage>,
-  include: Vec<String>,
-  exclude: Vec<String>,
-) -> Vec<ScriptCoverage> {
-  let include: Vec<Regex> =
-    include.iter().map(|e| Regex::new(e).unwrap()).collect();
-
-  let exclude: Vec<Regex> =
-    exclude.iter().map(|e| Regex::new(e).unwrap()).collect();
-
-  coverages
-    .into_iter()
-    .filter(|e| {
-      let is_internal = e.url.starts_with("deno:")
-        || e.url.ends_with("__anonymous__")
-        || e.url.ends_with("$deno$test.js");
-
-      let is_included = include.iter().any(|p| p.is_match(&e.url));
-      let is_excluded = exclude.iter().any(|p| p.is_match(&e.url));
-
-      (include.is_empty() || is_included) && !is_excluded && !is_internal
-    })
-    .collect::<Vec<ScriptCoverage>>()
-}
-
-pub async fn cover_files(
-  flags: Flags,
-  coverage_flags: CoverageFlags,
-) -> Result<(), AnyError> {
-  let ps = ProcState::build(flags).await?;
-
-  let script_coverages =
-    collect_coverages(coverage_flags.files, coverage_flags.ignore)?;
-  let script_coverages = filter_coverages(
-    script_coverages,
-    coverage_flags.include,
-    coverage_flags.exclude,
-  );
-
-  let reporter_kind = if coverage_flags.lcov {
-    CoverageReporterKind::Lcov
-  } else {
-    CoverageReporterKind::Pretty
-  };
-
-  let mut reporter = create_reporter(reporter_kind);
-
-  for script_coverage in script_coverages {
-    let module_specifier =
-      deno_core::resolve_url_or_path(&script_coverage.url)?;
-
-    let maybe_file = if module_specifier.scheme() == "file" {
-      ps.file_fetcher.get_source(&module_specifier)
-    } else {
-      ps.file_fetcher
-        .fetch_cached(&module_specifier, 10)
-        .with_context(|| {
-          format!("Failed to fetch \"{}\" from cache.", module_specifier)
-        })?
-    };
-    let file = maybe_file.ok_or_else(|| {
-      anyhow!("Failed to fetch \"{}\" from cache. 
-          Before generating coverage report, run `deno test --coverage` to ensure consistent state.", 
-          module_specifier
-        )
-    })?;
-
-    // Check if file was transpiled
-    let transpiled_source = match file.media_type {
-      MediaType::JavaScript
-      | MediaType::Unknown
-      | MediaType::Cjs
-      | MediaType::Mjs
-      | MediaType::Json => file.source.as_ref().clone(),
-      MediaType::Dts | MediaType::Dmts | MediaType::Dcts => "".to_string(),
-      MediaType::TypeScript
-      | MediaType::Jsx
-      | MediaType::Mts
-      | MediaType::Cts
-      | MediaType::Tsx => {
-        let emit_path = ps
-          .dir
-          .gen_cache
-          .get_cache_filename_with_extension(&file.specifier, "js")
-          .unwrap_or_else(|| {
-            unreachable!("Unable to get cache filename: {}", &file.specifier)
-          });
-        match ps.dir.gen_cache.get(&emit_path) {
-          Ok(b) => String::from_utf8(b).unwrap(),
-          Err(_) => {
-            return Err(anyhow!(
-              "Missing transpiled source code for: \"{}\".
-              Before generating coverage report, run `deno test --coverage` to ensure consistent state.",
-              file.specifier,
-            ))
-          }
-        }
-      }
-      MediaType::Wasm | MediaType::TsBuildInfo | MediaType::SourceMap => {
-        unreachable!()
-      }
-    };
-
-    let original_source = &file.source;
-    let maybe_source_map = ps.get_source_map(&script_coverage.url);
-
-    let coverage_report = generate_coverage_report(
-      &script_coverage,
-      &transpiled_source,
-      &maybe_source_map,
-    );
-
-    reporter.report(&coverage_report, original_source);
-  }
-
-  reporter.done();
-
-  Ok(())
-}