russell@unturf.com 6f11fb7598 xtuple: 5-MOAD scan; xtuple-0001 CWE-407 orutils missingParamList QStringList::contains O(P*M) 52x at P=1000

Scanned xTuple OpenRPT (public C++/Qt report engine used by xTuple ERP).
One MOAD-0001 defect found in orutils.cpp SQL parameter parsing loop.
MOADs 0002/0003/0004/0005 CLEAN.

2026-04-03 14:01:48 -04:00

1.9 KiB

Raw Permalink Blame History

xtuple-0001: orutils.cpp missingParamList QStringList::contains O(P*M) in SQL param parse loop

Project: xTuple / OpenRPT (open-source ERP report engine) File: OpenRPT/renderer/orutils.cpp MOAD: 0001 (CWE-407 — Inefficient Algorithmic Complexity) Severity: LOW-MEDIUM Speedup: ~10-50x at P=1000, M=500

Description

orQuery::orQuery() parses a SQL string to find parameter placeholders ($"name" and %N style). As it encounters each placeholder, it checks whether the parameter name is already in missingParamList before appending:

// OpenRPT/renderer/orutils.cpp:65
if(!missingParamList.contains(n))
    missingParamList.append(n);

missingParamList is declared as QStringList (i.e. QList<QString>). QStringList::contains() is a linear O(M) scan where M is our current missing param count. The outer loop iterates P times (once per param placeholder in the SQL). Total complexity: O(P * M).

For a parametric report template with hundreds of placeholder occurrences and many distinct missing params (e.g., a batch report runner that pre-scans many SQL templates), this compounds into measurable overhead.

Fix

Replace the membership check with a QSet<QString> shadow set for O(1) average-case lookup, while keeping missingParamList as the ordered QStringList for downstream consumption (it is a public member used by callers to display ordered missing-param dialogs).

QSet<QString> missingParamSet;
// ...
if(!missingParamSet.contains(n)) {
    missingParamSet.insert(n);
    missingParamList.append(n);
}

Complexity

Version	Time
Before	O(P * M)
After	O(P) amortized

Affected File

OpenRPT/renderer/orutils.cpp (and orutils.h for the shadow set field)

Test

defects/xtuple-0001/test/test_xtuple_0001.py — simulates the pattern in Python, benchmarks N=1000 param slots with M=500 distinct missing params, asserts speedup > 3x.

1.9 KiB Raw Permalink Blame History