mirror of
https://github.com/discourse/discourse.git
synced 2026-03-04 01:15:08 +08:00
53668b23a1
The ONP diff algorithm could run for an extremely long time on pathological inputs (e.g. fully replaced or random content), causing request timeouts and high CPU usage. The previous safeguard (`p >= 1000`) did not reliably bound work. Replace it with an explicit comparison budget that caps the number of element comparisons in the inner `snake` loop. The budget scales linearly with input size (default factor: 200× combined length, ceiling: 2 000 000 comparisons). When exceeded, a new `DiffLimitExceeded` exception is raised. Handle the new exception gracefully at every call site: - PostsController#revisions / #latest_revision → 422 with message - StaffActionLogsController#diff → inline fallback message - PostRevisor#compute_diff_size → treat as Infinity (forces new version) - discourse-ai UpdateArtifact → fallback diff block Also adds a pathology benchmark script and comprehensive test coverage for all affected paths. Co-authored-by: Sam Saffron <sam.saffron@gmail.com>
83 lines
2.5 KiB
Ruby
83 lines
2.5 KiB
Ruby
# frozen_string_literal: true
|
|
|
|
RSpec.describe ONPDiff do
|
|
describe "diff" do
|
|
it "returns an empty array when there is no content to diff" do
|
|
expect(ONPDiff.new("", "").diff).to eq([])
|
|
end
|
|
|
|
it "returns an array with the operation code for each element" do
|
|
expect(ONPDiff.new("abcd", "abef").diff).to eq(
|
|
[["a", :common], ["b", :common], ["e", :add], ["f", :add], ["c", :delete], ["d", :delete]],
|
|
)
|
|
end
|
|
|
|
it "raises when comparison budget is exceeded" do
|
|
diff = ONPDiff.new("abcd", "wxyz", comparison_budget_factor: 1, max_comparison_budget: 2)
|
|
|
|
expect { diff.diff }.to raise_error(ONPDiff::DiffLimitExceeded)
|
|
expect(diff.comparison_budget).to eq(2)
|
|
expect(diff.comparisons_used).to eq(3)
|
|
end
|
|
end
|
|
|
|
describe "short_diff" do
|
|
it "returns an empty array when there is no content to diff" do
|
|
expect(ONPDiff.new("", "").short_diff).to eq([])
|
|
end
|
|
|
|
it "returns an array with the operation code for each element" do
|
|
expect(ONPDiff.new("abc", "acd").short_diff).to eq(
|
|
[["a", :common], ["b", :delete], ["c", :common], ["d", :add]],
|
|
)
|
|
end
|
|
|
|
it "returns an array with sequentially similar operations merged" do
|
|
expect(ONPDiff.new("abcd", "abef").short_diff).to eq(
|
|
[["ab", :common], ["ef", :add], ["cd", :delete]],
|
|
)
|
|
end
|
|
end
|
|
|
|
describe "paragraph_diff" do
|
|
it "returns an empty array when there is no content to diff" do
|
|
expect(ONPDiff.new("", "").paragraph_diff).to eq([])
|
|
end
|
|
|
|
it "returns an array with the operation code for each element" do
|
|
expect(ONPDiff.new("abc", "acd").paragraph_diff).to eq(
|
|
[["a", :common], ["b", :delete], ["c", :common], ["d", :add]],
|
|
)
|
|
end
|
|
|
|
it "pairs as many elements as possible" do
|
|
expect(ONPDiff.new("abcd", "abef").paragraph_diff).to eq(
|
|
[["a", :common], ["b", :common], ["e", :add], ["c", :delete], ["f", :add], ["d", :delete]],
|
|
)
|
|
|
|
expect(ONPDiff.new("abcde", "abfg").paragraph_diff).to eq(
|
|
[
|
|
["a", :common],
|
|
["b", :common],
|
|
["c", :delete],
|
|
["d", :delete],
|
|
["f", :add],
|
|
["e", :delete],
|
|
["g", :add],
|
|
],
|
|
)
|
|
|
|
expect(ONPDiff.new("abcd", "abefg").paragraph_diff).to eq(
|
|
[
|
|
["a", :common],
|
|
["b", :common],
|
|
["e", :add],
|
|
["f", :add],
|
|
["c", :delete],
|
|
["g", :add],
|
|
["d", :delete],
|
|
],
|
|
)
|
|
end
|
|
end
|
|
end
|
