However, they are only FPs because the input cannot contain newlines, so I'm not sure how we should handle that.

Yeah that's a bit tricky, but I think it might be worth special-casing the handling of .*$ against URL sources.

The way I see it, if $ is preceded by a universal regexp term (a term that matches anything), then the $ is guaranteed to match the empty string, and the not matchesEpsilon(succ) condition should morally have failed but actually passed, leading to the FP. We could generalize the predicate to look for universal regexps, but that still wouldn't handle .* because it's not truly universal, so we need a way to defer the check once we know the source.

We can convert the succ variable in the PolynomialBackTrackingTerm charpred to a field, which is easy because it's a top-level exists in the charpred (pasted below for reference):

class PolynomialBackTrackingTerm extends InfiniteRepetitionQuantifier {
  string reason;
  PolynomialBackTrackingTerm() {
    // the regexp may fail to match ...
    exists(RegExpTerm succ | this.getSuccessor+() = succ | not matchesEpsilon(succ)) and

If I understand correctly, we use succ as sort of a witness that the regexp may yet fail to match after matching this. In our example $ is the witness.

If the taint source is found to be a RequestInputAccess with getKind() = "url", we then require that the witness is not a $ immediately preceded by .*. (Or, as there can be multiple witnesses in general, at least one witness must not be such a $).

If I understand correctly, we use succ as sort of a witness that the regexp may yet fail to match after matching this

Correct. The regexp engine will then try all of the N^2 sequences that lead to that unsatisfiable succ before finally giving up.

Yeah that's a bit tricky, but I think it might be worth special-casing the handling of .*$ against URL sources.

I'll try to do that.

If I understand correctly, we use succ as sort of a witness that the regexp may yet fail to match after matching this

Correct. The regexp engine will then try all of the N^2 sequences that lead to that unsatisfiable succ before finally giving up.

I've found the Regex Debugger on regex101.com quite helpful in understanding regexp performance.
(Link to regex with quadratic performance: https://regex101.com/r/JHUvrh/1/debugger)

Yeah that's a bit tricky, but I think it might be worth special-casing the handling of .*$ against URL sources.

I've done it now. But I'm not proud of the implementation.

I did the pruning of results in the where clause.
Because the only other way I see is to use flow-labels.
And I don't want to introduce flow-labels to this query just to support that case.