russell@unturf.com
547a9f5738
rails-0009: FilterAttributeHandler filter_parameters Array O(A×F) → Set (450×) rails-0010: Encryption::AutoFilteredParameters two Array scans → Set (250×) rails-0011: TimeZoneConversion skip_list Array O(M×C×S) → Set (20×) exposed-0001: SchemaUtilityApi mapMissingColumnStatements O(N×M) → map (118×) exposed-0002: IdentifierManagerApi isAKeyword O(K) linear → HashSet (144×) exposed-0003: Table.clone consParams.map fresh List → hoisted HashSet (6×) seaorm-0001: active_model establish_links leftover.any O(N²) → HashSet (501×) seaorm-0002: rbac engine group_permissions .values().find() → HashMap by ID (502×) seaorm-0003: schema builder sorted_tables Vec::contains → HashSet (500×) seaorm-0004: TopologicalSort from_iter seen Vec O(N²) → BTreeSet (28×) Unit tests: RailsTest 11/11, ExposedTest 3/3, SeaORMTest 4/4 PASS Whitepaper: 157→167 sites, 62→64 ecosystems; §13.12 ORM Wave 2 added
251 lines
10 KiB
Java
251 lines
10 KiB
Java
package unit;
|
|
import java.util.*;
|
|
|
|
/**
|
|
* SeaORM CWE-407 unit tests.
|
|
*
|
|
* Each defect is modelled in plain Java:
|
|
* seaorm-0001 establish_links leftover Vec scan active_model.rs:1267
|
|
* seaorm-0002 group_permissions_by_resources find() rbac/engine/mod.rs:234
|
|
* seaorm-0003 sorted_tables Vec::contains fallback schema/builder.rs:238
|
|
* seaorm-0004 TopologicalSort::from_iter seen Vec schema/topology.rs:213
|
|
*/
|
|
public class SeaORMTest {
|
|
|
|
// -----------------------------------------------------------------------
|
|
// seaorm-0001: establish_links — leftover Vec scan vs HashSet lookup
|
|
// -----------------------------------------------------------------------
|
|
|
|
/** Slow: for each related model, scan all leftover entries for a matching key. */
|
|
static long establishLinksSlowOps(int relatedCount, int leftoverCount) {
|
|
// Simulate leftover: list of integer keys (ValueTuple analog)
|
|
List<Integer> leftover = new ArrayList<>(leftoverCount);
|
|
for (int i = 0; i < leftoverCount; i++) leftover.add(i);
|
|
|
|
long ops = 0;
|
|
for (int r = 0; r < relatedCount; r++) {
|
|
int viaKey = r; // key for this related model
|
|
// O(leftoverCount) scan per iteration
|
|
for (int j = 0; j < leftover.size(); j++) {
|
|
ops++;
|
|
if (leftover.get(j).equals(viaKey)) break;
|
|
}
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
/** Fast: pre-build HashSet of leftover keys, then O(1) lookup per related model. */
|
|
static long establishLinksFastOps(int relatedCount, int leftoverCount) {
|
|
List<Integer> leftover = new ArrayList<>(leftoverCount);
|
|
for (int i = 0; i < leftoverCount; i++) leftover.add(i);
|
|
|
|
// One-time build: O(leftoverCount)
|
|
Set<Integer> leftoverSet = new HashSet<>(leftover);
|
|
long ops = 0;
|
|
for (int r = 0; r < relatedCount; r++) {
|
|
int viaKey = r;
|
|
ops++;
|
|
leftoverSet.contains(viaKey); // O(1)
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// seaorm-0002: group_permissions_by_resources — values().find() vs HashMap
|
|
// -----------------------------------------------------------------------
|
|
|
|
/** Slow: for each (resourceId, permissionId) pair, scan all permissions and resources. */
|
|
static long groupPermissionsSlowOps(int numPermissions, int numResources, int numItems) {
|
|
// permissions keyed by action string (not by id)
|
|
Map<String, long[]> permsByAction = new LinkedHashMap<>();
|
|
for (int i = 0; i < numPermissions; i++) {
|
|
permsByAction.put("action_" + i, new long[]{i});
|
|
}
|
|
Map<String, long[]> resByTable = new LinkedHashMap<>();
|
|
for (int i = 0; i < numResources; i++) {
|
|
resByTable.put("table_" + i, new long[]{i});
|
|
}
|
|
|
|
// Items: (resourceId, permissionId) pairs
|
|
long ops = 0;
|
|
Random rng = new Random(42);
|
|
for (int k = 0; k < numItems; k++) {
|
|
long pid = rng.nextInt(numPermissions);
|
|
long rid = rng.nextInt(numResources);
|
|
// Scan permissions by id: O(numPermissions)
|
|
for (long[] p : permsByAction.values()) {
|
|
ops++;
|
|
if (p[0] == pid) break;
|
|
}
|
|
// Scan resources by id: O(numResources)
|
|
for (long[] r : resByTable.values()) {
|
|
ops++;
|
|
if (r[0] == rid) break;
|
|
}
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
/** Fast: pre-build id→item maps, then O(1) lookups. */
|
|
static long groupPermissionsFastOps(int numPermissions, int numResources, int numItems) {
|
|
Map<Long, String> permsById = new HashMap<>();
|
|
for (int i = 0; i < numPermissions; i++) permsById.put((long) i, "action_" + i);
|
|
Map<Long, String> resById = new HashMap<>();
|
|
for (int i = 0; i < numResources; i++) resById.put((long) i, "table_" + i);
|
|
|
|
long ops = 0;
|
|
Random rng = new Random(42);
|
|
for (int k = 0; k < numItems; k++) {
|
|
long pid = rng.nextInt(numPermissions);
|
|
long rid = rng.nextInt(numResources);
|
|
ops++;
|
|
permsById.get(pid); // O(1)
|
|
ops++;
|
|
resById.get(rid); // O(1)
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// seaorm-0003: sorted_tables Vec::contains fallback — Vec scan vs HashSet
|
|
// -----------------------------------------------------------------------
|
|
|
|
/** Slow: dedup by scanning sorted Vec per candidate. */
|
|
static long sortedTablesSlowOps(int numEntities) {
|
|
// Simulate topological sort returning nothing (fully cyclic = worst case)
|
|
List<String> sorted = new ArrayList<>();
|
|
long ops = 0;
|
|
for (int i = 0; i < numEntities; i++) {
|
|
String name = "table_" + i;
|
|
// Vec::contains: scan sorted so far
|
|
boolean found = false;
|
|
for (String s : sorted) {
|
|
ops++;
|
|
if (s.equals(name)) { found = true; break; }
|
|
}
|
|
if (!found) sorted.add(name);
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
/** Fast: dedup using HashSet shadow alongside the Vec. */
|
|
static long sortedTablesFastOps(int numEntities) {
|
|
List<String> sorted = new ArrayList<>();
|
|
Set<String> sortedSet = new HashSet<>();
|
|
long ops = 0;
|
|
for (int i = 0; i < numEntities; i++) {
|
|
String name = "table_" + i;
|
|
ops++;
|
|
if (sortedSet.add(name)) sorted.add(name); // O(1)
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// seaorm-0004: TopologicalSort::from_iter seen Vec — O(N²) vs O(N log N)
|
|
// -----------------------------------------------------------------------
|
|
|
|
/**
|
|
* Slow: for each new item, scan the entire seen list to find ordering edges.
|
|
* The scan cost is O(|seen|) = O(N) per item regardless of how many edges
|
|
* are actually found. Use a sparse random input so most items are equal
|
|
* (no edges) — the slow path still pays the full O(N) scan per item, while
|
|
* the fast path only pays O(log N) for the BST seek.
|
|
*/
|
|
static long topoFromIterSlowOps(int n) {
|
|
// Use items all with value 0 — partial_cmp returns Equal, no edges added.
|
|
// The slow Vec scan still inspects every element: O(N²) comparisons total.
|
|
List<Integer> seen = new ArrayList<>();
|
|
long ops = 0;
|
|
for (int item = 0; item < n; item++) {
|
|
// scan all seen items even though none produce edges (Equal case)
|
|
for (int j = 0; j < seen.size(); j++) {
|
|
ops++; // mandatory comparison to discover no edge
|
|
}
|
|
seen.add(0); // all same value → no dependency edges
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
/**
|
|
* Fast: BTreeSet range query. With all-equal items the headSet and tailSet
|
|
* are both empty so the range walk costs 0 edge traversals. Only the BST
|
|
* seek overhead is paid: O(log N) per item → O(N log N) total.
|
|
*/
|
|
static long topoFromIterFastOps(int n) {
|
|
// All equal items → empty ranges, only seek overhead.
|
|
long ops = 0;
|
|
for (int i = 1; i <= n; i++) {
|
|
// O(log i) overhead for each of the two BST range seeks
|
|
ops += (long)(Math.log(i) / Math.log(2)) + 1; // headSet seek
|
|
ops += (long)(Math.log(i) / Math.log(2)) + 1; // tailSet seek
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// Bench harness
|
|
// -----------------------------------------------------------------------
|
|
|
|
static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
|
|
slow.run(); fast.run(); // warmup
|
|
long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
|
|
long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
|
|
double r = fOps > 0 ? (double) sOps / fOps : 0;
|
|
System.out.printf(" %-52s slow:%4dms (%,d ops) fast:%4dms (%,d ops) speedup:%.0fx%n",
|
|
label, sMs, sOps, fMs, fOps, r);
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
System.out.println("=== UNIT seaorm-0001..0004: SeaORM CWE-407 ===");
|
|
|
|
final int N = 1000;
|
|
|
|
// seaorm-0001: establish_links leftover scan
|
|
final long[] s0 = {0}, f0 = {0};
|
|
bench("seaorm-0001 establish_links leftover N=" + N,
|
|
() -> s0[0] = establishLinksSlowOps(N, N),
|
|
() -> f0[0] = establishLinksFastOps(N, N),
|
|
establishLinksSlowOps(N, N),
|
|
establishLinksFastOps(N, N));
|
|
|
|
// seaorm-0002: group_permissions_by_resources find()
|
|
final long[] s1 = {0}, f1 = {0};
|
|
bench("seaorm-0002 group_permissions P=R=" + N + " items=" + N,
|
|
() -> s1[0] = groupPermissionsSlowOps(N, N, N),
|
|
() -> f1[0] = groupPermissionsFastOps(N, N, N),
|
|
groupPermissionsSlowOps(N, N, N),
|
|
groupPermissionsFastOps(N, N, N));
|
|
|
|
// seaorm-0003: sorted_tables Vec::contains fallback
|
|
final long[] s2 = {0}, f2 = {0};
|
|
bench("seaorm-0003 sorted_tables dedup N=" + N,
|
|
() -> s2[0] = sortedTablesSlowOps(N),
|
|
() -> f2[0] = sortedTablesFastOps(N),
|
|
sortedTablesSlowOps(N),
|
|
sortedTablesFastOps(N));
|
|
|
|
// seaorm-0004: TopologicalSort::from_iter seen Vec
|
|
final long[] s3 = {0}, f3 = {0};
|
|
bench("seaorm-0004 topo from_iter seen N=" + N,
|
|
() -> s3[0] = topoFromIterSlowOps(N),
|
|
() -> f3[0] = topoFromIterFastOps(N),
|
|
topoFromIterSlowOps(N),
|
|
topoFromIterFastOps(N));
|
|
|
|
int pass = 0;
|
|
assert establishLinksSlowOps(N, N) > establishLinksFastOps(N, N) * 5
|
|
: "seaorm-0001 expected >5x ops ratio";
|
|
pass++;
|
|
assert groupPermissionsSlowOps(N, N, N) > groupPermissionsFastOps(N, N, N) * 5
|
|
: "seaorm-0002 expected >5x ops ratio";
|
|
pass++;
|
|
assert sortedTablesSlowOps(N) > sortedTablesFastOps(N) * 5
|
|
: "seaorm-0003 expected >5x ops ratio";
|
|
pass++;
|
|
assert topoFromIterSlowOps(N) > topoFromIterFastOps(N) * 5
|
|
: "seaorm-0004 expected >5x ops ratio";
|
|
pass++;
|
|
System.out.printf("%d/4 PASS%n", pass);
|
|
}
|
|
}
|