Repository: dart-lang/pana (dart)

Issue:
Implement/use token-based diff algorithm for license diffs
#1485 introduces a token-based longest common subsequence calculation. With that, we will have two diffs algorithms, and we should replace the current text-based with the token-based algorithm.

Pull request:
- Closes #1487 (as won't implement).
- I've tried to adopt some of the text-diff algorithm optimizations on the token lists (e.g. breadth-first search), but I couldn't really approach its speed (probably the object allocation was more costly than the algorithm's comparison operations).
- Instead, this will remove the token-based LCS, instead, it uses a lazy reconstruction of the token operations. The lazy part is needed, as the algorithm runs on multiple license candidates, while the coverage calculation is only run on the few final ones.

Patch:
diff --git a/lib/src/license.dart b/lib/src/license.dart
index a597adf21..8bf8e1809 100644
--- a/lib/src/license.dart
+++ b/lib/src/license.dart
@@ -10,7 +10,6 @@ import 'package:meta/meta.dart';
 import 'package:path/path.dart' as p;
 import 'package:source_span/source_span.dart';
 
-import 'license_detection/lcs.dart';
 import 'license_detection/license_detector.dart' hide License, Range;
 import 'model.dart';
 
@@ -58,14 +57,7 @@ Future<List<License>> detectLicenseInContent(
   }
 
   List<int> buildCoverages(LicenseMatch match) {
-    final ops = calculateTokenEditOps(
-      // ignore: invalid_use_of_visible_for_testing_member
-      unknown: match.tokens,
-      // ignore: invalid_use_of_visible_for_testing_member
-      known: match.license.tokens,
-    );
-
-    return ops
+    return match.tokenOps
         .whereType<MatchOp>()
         .expand(
           (op) => [
diff --git a/lib/src/license_detection/confidence.dart b/lib/src/license_detection/confidence.dart
index 114ac4ac8..adedc493f 100644
--- a/lib/src/license_detection/confidence.dart
+++ b/lib/src/license_detection/confidence.dart
@@ -35,8 +35,7 @@ LicenseMatch licenseMatch(
       "Can't compare the licenses due to different granularity",
     );
   }
-  // TODO: use the token-based LCS algorithm from `lcs.dart` (https://github.com/dart-lang/pana/issues/1487)
-  final diffs = getDiffs(
+  final (diffs, tokenOpsFn) = getDiffs(
     unknownLicense.tokens,
     knownLicense.tokens,
     matchRange,
@@ -68,6 +67,7 @@ LicenseMatch licenseMatch(
     confidence,
     knownLicense,
     diffs,
+    tokenOpsFn,
     Range(range.start, range.end),
   );
 }
@@ -86,24 +86,97 @@ double confidencePercentage(int knownLength, int distance) {
 }
 
 @visibleForTesting
-List<Diff> getDiffs(
+(List<Diff>, TokenOpsFn) getDiffs(
   List<Token> inputTokens,
   List<Token> knownTokens,
   MatchRange matchRange,
 ) {
-  final unknownText = normalizedContent(
-    inputTokens
-        .skip(matchRange.input.start)
-        .take(matchRange.input.end - matchRange.input.start),
-  );
+  final filteredInputTokens = inputTokens
+      .skip(matchRange.input.start)
+      .take(matchRange.input.end - matchRange.input.start)
+      .toList();
+  final unknownText = normalizedContent(filteredInputTokens);
 
-  final knownText = normalizedContent(knownTokens.take(matchRange.source.end));
+  final filteredKnownTokens = knownTokens.take(matchRange.source.end).toList();
+  final knownText = normalizedContent(filteredKnownTokens);
 
   final diffs = diffMain(unknownText, knownText);
 
   diffCleanupEfficiency(diffs);
 
-  return List.unmodifiable(diffs);
+  /// Lazily builds a list of [TokenOp] from the text-based diffs, re-tracking
+  /// the origin of the characters to tokens.
+  ///
+  /// Note: the text diff algorighm calculated the operations as updates to the
+  ///       known license file, while these fields represent the changes from
+  ///       the unknown input, to be easier to display the difference overlayed
+  ///       on that text.
+  ///
+  /// TODO: consider updating the parameter order + post-verification so that we don't need to flip the edit direction
+  List<TokenOp> tokenOpsFn() {
+    final inputPositions = _tokenPositions(
+      filteredInputTokens,
+      unknownText.length,
+    );
+    final knownPositions = _tokenPositions(
+      filteredKnownTokens,
+      knownText.length,
+    );
+    var inputOffset = 0;
+    var knownOffset = 0;
+    return diffs.map((diff) {
+      switch (diff.operation) {
+        case Operation.equal:
+          final inputend =
+              inputPositions[inputOffset + diff.text.length - 1] + 1;
+          final tokensFromInput = filteredInputTokens.sublist(
+            inputPositions[inputOffset],
+            inputend,
+          );
+          final tokensFromKnown = filteredKnownTokens.sublist(
+            knownPositions[knownOffset],
+            knownPositions[knownOffset] + tokensFromInput.length,
+          );
+          inputOffset += diff.text.length;
+          knownOffset += diff.text.length;
+          return MatchOp(
+            tokensFromInput
+                .mapIndexed((i, t) => (unknown: t, known: tokensFromKnown[i]))
+                .toList(),
+          );
+        case Operation.delete:
+          final end = inputPositions[inputOffset + diff.text.length - 1] + 1;
+          final tokensFromInput = filteredInputTokens.sublist(
+            inputPositions[inputOffset],
+            end,
+          );
+          inputOffset += diff.text.length;
+          return InsertOp(tokensFromInput);
+
+        case Operation.insert:
+          final end = knownPositions[knownOffset + diff.text.length - 1] + 1;
+          final tokensFromKnown = filteredKnownTokens.sublist(
+            knownPositions[knownOffset],
+            end,
+          );
+          knownOffset += diff.text.length;
+          return DeleteOp(tokensFromKnown);
+      }
+    }).toList();
+  }
+
+  return (List.unmodifiable(diffs), tokenOpsFn);
+}
+
+List<int> _tokenPositions(Iterable<Token> tokens, int length) {
+  final positions = List.filled(length + 1, -1);
+  var index = 0;
+  for (final entry in tokens.indexed) {
+    for (var i = entry.$2.value.length; i >= 0; i--) {
+      positions[index++] = entry.$1;
+    }
+  }
+  return positions;
 }
 
 /// Returns the range in [diffs] that best resembles the known license text.
diff --git a/lib/src/license_detection/lcs.dart b/lib/src/license_detection/lcs.dart
deleted file mode 100644
index 1e2518186..000000000
--- a/lib/src/license_detection/lcs.dart
+++ /dev/null
@@ -1,185 +0,0 @@
-// Copyright (c) 2025, the Dart project authors.  Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-
-// ignore_for_file: invalid_use_of_visible_for_testing_member
-
-import 'dart:math';
-
-import 'license_detector.dart' show Token;
-
-/// A pair representing matching tokens from unknown to known sequences.
-typedef TokenPair = ({Token unknown, Token known});
-
-/// Describes an edit operation on the token list.
-abstract class TokenOp {}
-
-/// Describes an insertion into the unknown tokens.
-class InsertOp extends TokenOp {
-  final List<Token> tokens;
-  InsertOp(this.tokens);
-}
-
-/// Describes a deletion from the known tokens.
-class DeleteOp extends TokenOp {
-  final List<Token> tokens;
-  DeleteOp(this.tokens);
-}
-
-/// Describes a match of token pairs.
-class MatchOp extends TokenOp {
-  final List<TokenPair> pairs;
-  MatchOp(this.pairs);
-}
-
-/// Calculates the difference between [unknown] and [known] token lists and creates
-/// a list of token-editing operations that are needed to transform the tokens from
-/// [known] to [unknown].
-List<TokenOp> calculateTokenEditOps({
-  required List<Token> unknown,
-  required List<Token> known,
-}) {
-  if (unknown.isEmpty && known.isEmpty) {
-    return [];
-  }
-  if (unknown.isEmpty) {
-    return [DeleteOp(known)];
-  }
-  if (known.isEmpty) {
-    return [InsertOp(unknown)];
-  }
-
-  final maxPrefixLength = min(unknown.length, known.length);
-  final matchedPrefix = <TokenPair>[];
-  for (var i = 0; i < maxPrefixLength; i++) {
-    final utoken = unknown[i];
-    final ktoken = known[i];
-    if (!utoken.matches(ktoken)) {
-      break;
-    }
-    matchedPrefix.add((unknown: utoken, known: ktoken));
-  }
-
-  final maxPostfixLength = maxPrefixLength - matchedPrefix.length;
-  final matchedPostfix = <TokenPair>[];
-  var matchedPostfixCount = 0;
-  for (var i = 1; i <= maxPostfixLength; i++) {
-    final utoken = unknown[unknown.length - i];
-    final ktoken = known[known.length - i];
-    if (!utoken.matches(ktoken)) {
-      break;
-    }
-    matchedPostfixCount++;
-  }
-  for (var i = matchedPostfixCount; i >= 1; i--) {
-    final utoken = unknown[unknown.length - i];
-    final ktoken = known[known.length - i];
-    matchedPostfix.add((unknown: utoken, known: ktoken));
-  }
-
-  List<Token> trimList(List<Token> list) {
-    if (matchedPrefix.isEmpty && matchedPostfix.isEmpty) {
-      return list;
-    }
-    return list
-        .skip(matchedPrefix.length)
-        .take(list.length - matchedPrefix.length - matchedPostfix.length)
-        .toList();
-  }
-
-  return <TokenOp>[
-    if (matchedPrefix.isNotEmpty) MatchOp(matchedPrefix),
-    ..._dynamicLcs(unknown: trimList(unknown), known: trimList(known)),
-    if (matchedPostfix.isNotEmpty) MatchOp(matchedPostfix),
-  ];
-}
-
-List<TokenOp> _dynamicLcs({
-  required List<Token> unknown,
-  required List<Token> known,
-}) {
-  if (unknown.isEmpty && known.isEmpty) {
-    return [];
-  }
-  if (unknown.isEmpty) {
-    return [DeleteOp(known)];
-  }
-  if (known.isEmpty) {
-    return [InsertOp(unknown)];
-  }
-
-  final m = unknown.length;
-  final n = known.length;
-
-  // table to store lengths of LCS
-  final table = List.generate(m + 1, (_) => List.filled(n + 1, 0));
-  for (var i = 1; i <= m; i++) {
-    for (var j = 1; j <= n; j++) {
-      if (unknown[i - 1].matches(known[j - 1])) {
-        table[i][j] = table[i - 1][j - 1] + 1;
-      } else {
-        table[i][j] = max(table[i - 1][j], table[i][j - 1]);
-      }
-    }
-  }
-
-  // backtrack to construct the operations
-  final opsBackwards = <TokenOp>[];
-  var i = m;
-  var j = n;
-
-  while (i > 0 || j > 0) {
-    // shortcut: only deletes left
-    if (i == 0) {
-      opsBackwards.add(DeleteOp(known.take(j).toList()));
-      break;
-    }
-    // shortcut: only inserts left
-    if (j == 0) {
-      opsBackwards.add(InsertOp(unknown.take(i).toList()));
-      break;
-    }
-
-    bool isMatch() => i > 0 && j > 0 && table[i][j] == table[i - 1][j - 1] + 1;
-    bool isInsert() => i > 0 && table[i - 1][j] >= table[i][j - 1]; // j != 0
-    bool isDelete() => j > 0 && table[i - 1][j] < table[i][j - 1]; // i != 0
-
-    if (isMatch()) {
-      // match found
-      final matchPairsBackwards = <TokenPair>[];
-      do {
-        matchPairsBackwards.add((unknown: unknown[i - 1], known: known[j - 1]));
-        i--;
-        j--;
-      } while (isMatch());
-      opsBackwards.add(MatchOp(matchPairsBackwards.reverseIfNeeded()));
-    } else if (isInsert()) {
-      // insert into unknown
-      final insertTokens = <Token>[];
-      do {
-        insertTokens.add(unknown[i - 1]);
-        i--;
-      } while (isInsert() && !isMatch());
-      opsBackwards.add(InsertOp(insertTokens.reverseIfNeeded()));
-    } else {
-      // delete from known
-      final deleteTokens = <Token>[];
-      do {
-        deleteTokens.add(known[j - 1]);
-        j--;
-      } while (isDelete() && !isMatch());
-      opsBackwards.add(DeleteOp(deleteTokens.reverseIfNeeded()));
-    }
-  }
-
-  return opsBackwards.reverseIfNeeded();
-}
-
-extension _ListExt<T> on List<T> {
-  List<T> reverseIfNeeded() {
-    if (length <= 1) {
-      return this;
-    }
-    return reversed.toList();
-  }
-}
diff --git a/lib/src/license_detection/license.dart b/lib/src/license_detection/license.dart
index 573dca7d3..9a238701a 100644
--- a/lib/src/license_detection/license.dart
+++ b/lib/src/license_detection/license.dart
@@ -109,6 +109,33 @@ class LicenseWithNGrams extends License {
   }
 }
 
+/// A callback to lazily calculate the list of token-based operations (prepared alongside the diff operation).
+typedef TokenOpsFn = List<TokenOp> Function();
+
+/// A pair representing matching tokens from unknown to known sequences.
+typedef TokenPair = ({Token unknown, Token known});
+
+/// Describes an edit operation on the token list.
+abstract class TokenOp {}
+
+/// Describes an insertion into the unknown tokens.
+class InsertOp extends TokenOp {
+  final List<Token> tokens;
+  InsertOp(this.tokens);
+}
+
+/// Describes a deletion from the known tokens.
+class DeleteOp extends TokenOp {
+  final List<Token> tokens;
+  DeleteOp(this.tokens);
+}
+
+/// Describes a match of token pairs.
+class MatchOp extends TokenOp {
+  final List<TokenPair> pairs;
+  MatchOp(this.pairs);
+}
+
 /// Contains details regarding the results of corpus license match with unknown text.
 @sealed
 class LicenseMatch {
@@ -120,6 +147,9 @@ class LicenseMatch {
   @visibleForTesting
   final List<Diff> diffs;
 
+  /// Callback to lazily calculate the list of token-based operations.
+  final TokenOpsFn _tokenOpsFn;
+
   /// Range of [diffs] which represents the diffs between known license and unknown license.
   ///
   /// Diffs lying outside of [diffRange] represent additional text in unknown license
@@ -173,9 +203,11 @@ class LicenseMatch {
     this.confidence,
     this.license,
     this.diffs,
+    TokenOpsFn tokenOpsFn,
     this.diffRange,
   ) : tokensClaimed = tokens.length,
-      tokenRange = Range(tokens.first.index, tokens.last.index);
+      tokenRange = Range(tokens.first.index, tokens.last.index),
+      _tokenOpsFn = tokenOpsFn;
 
   @visibleForTesting
   LicenseMatch.createInstance(
@@ -184,9 +216,10 @@ class LicenseMatch {
     this.tokensClaimed,
     this.diffRange,
     this.diffs,
+    TokenOpsFn tokenOpsFn,
     this.license,
     this.tokenRange,
-  );
+  ) : _tokenOpsFn = tokenOpsFn;
 
   LicenseMatch updateTokenIndex(int startIndex, int endIndex) {
     return LicenseMatch.createInstance(
@@ -195,6 +228,7 @@ class LicenseMatch {
       endIndex - startIndex,
       diffRange,
       diffs,
+      _tokenOpsFn,
       license,
       Range(startIndex, endIndex),
     );
@@ -207,6 +241,9 @@ class LicenseMatch {
   /// Token density is the product of number of tokens claimed in
   /// the range and confidence score of the match.
   late final tokenDensity = tokensClaimed * confidence;
+
+  /// The list of token based operations.
+  late final tokenOps = _tokenOpsFn();
 }
 
 /// Generates a frequency table for the given list of [tokens].
diff --git a/lib/src/license_detection/license_detector.dart b/lib/src/license_detection/license_detector.dart
index 1db864a3f..a7028e2b7 100644
--- a/lib/src/license_detection/license_detector.dart
+++ b/lib/src/license_detection/license_detector.dart
@@ -7,6 +7,7 @@ import 'dart:io';
 import 'dart:isolate';
 import 'dart:math';
 
+import 'package:collection/collection.dart';
 import 'package:meta/meta.dart';
 import 'package:source_span/source_span.dart';
 import 'package:string_scanner/string_scanner.dart';


Test patch:
diff --git a/test/goldens/end2end/_dummy_pkg-1.0.0-null-safety.1.json b/test/goldens/end2end/_dummy_pkg-1.0.0-null-safety.1.json
index 66d4f2476..5ba783881 100644
--- a/test/goldens/end2end/_dummy_pkg-1.0.0-null-safety.1.json
+++ b/test/goldens/end2end/_dummy_pkg-1.0.0-null-safety.1.json
@@ -38,7 +38,7 @@
         "coverages": [
           63,
           596,
-          609,
+          604,
           1523
         ]
       }
@@ -117,7 +117,7 @@
           "coverages": [
             63,
             596,
-            609,
+            604,
             1523
           ]
         }
diff --git a/test/goldens/end2end/async-2.11.0.json b/test/goldens/end2end/async-2.11.0.json
index cc15814ca..670e84e27 100644
--- a/test/goldens/end2end/async-2.11.0.json
+++ b/test/goldens/end2end/async-2.11.0.json
@@ -48,7 +48,7 @@
         "coverages": [
           44,
           577,
-          589,
+          585,
           1503
         ]
       }
@@ -155,7 +155,7 @@
           "coverages": [
             44,
             577,
-            589,
+            585,
             1503
           ]
         }
diff --git a/test/goldens/end2end/http-0.13.0.json b/test/goldens/end2end/http-0.13.0.json
index 69402bbcc..2c4f95528 100644
--- a/test/goldens/end2end/http-0.13.0.json
+++ b/test/goldens/end2end/http-0.13.0.json
@@ -48,7 +48,7 @@
         "coverages": [
           63,
           596,
-          609,
+          604,
           1523
         ]
       }
@@ -161,7 +161,7 @@
           "coverages": [
             63,
             596,
-            609,
+            604,
             1523
           ]
         }
diff --git a/test/goldens/end2end/lints-1.0.0.json b/test/goldens/end2end/lints-1.0.0.json
index 59da17d5f..b860e891e 100644
--- a/test/goldens/end2end/lints-1.0.0.json
+++ b/test/goldens/end2end/lints-1.0.0.json
@@ -37,7 +37,7 @@
         "coverages": [
           43,
           576,
-          588,
+          584,
           1502
         ]
       }
@@ -128,7 +128,7 @@
           "coverages": [
             43,
             576,
-            588,
+            584,
             1502
           ]
         }
diff --git a/test/goldens/end2end/url_launcher-6.3.1.json b/test/goldens/end2end/url_launcher-6.3.1.json
index 38d0e84db..c2e907c73 100644
--- a/test/goldens/end2end/url_launcher-6.3.1.json
+++ b/test/goldens/end2end/url_launcher-6.3.1.json
@@ -90,7 +90,7 @@
         "coverages": [
           58,
           591,
-          604,
+          599,
           1518
         ]
       }
@@ -211,7 +211,7 @@
           "coverages": [
             58,
             591,
-            604,
+            599,
             1518
           ]
         }
diff --git a/test/license_detector_test.dart b/test/license_detector_test.dart
index aee61d283..e7f586623 100644
--- a/test/license_detector_test.dart
+++ b/test/license_detector_test.dart
@@ -326,6 +326,7 @@ LicenseMatch _dummyLicenseMatchInstance(
     tokensClaimed,
     diffRange ?? dummyDiffRange,
     [],
+    () => [],
     LicenseWithNGrams.parse(
       License.parse(identifier: identifier, content: 'take some text'),
       3,