1#************************************************************** 2# 3# Licensed to the Apache Software Foundation (ASF) under one 4# or more contributor license agreements. See the NOTICE file 5# distributed with this work for additional information 6# regarding copyright ownership. The ASF licenses this file 7# to you under the Apache License, Version 2.0 (the 8# "License"); you may not use this file except in compliance 9# with the License. You may obtain a copy of the License at 10# 11# http://www.apache.org/licenses/LICENSE-2.0 12# 13# Unless required by applicable law or agreed to in writing, 14# software distributed under the License is distributed on an 15# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16# KIND, either express or implied. See the License for the 17# specific language governing permissions and limitations 18# under the License. 19# 20#************************************************************** 21 22# usage: formulacheck.py <outdir> <formulas.json> 23# ODF 1.2 Part 1 2.2.1 D.3 and 2.2.4 D/E: the style:condition, table:condition, table:expression, 24# table:formula and text:formula values are parsed with the OpenFormula grammar (Part 2 chapter 5) 25# and the condition syntaxes of Part 1 19.468 and 19.596. Syntax only: no semantics, no function arity. 26# Findings are "shall: [rule] ..." or "should: [rule] ...". 27import sys, os, re, json, zipfile, collections, unicodedata 28from xml.parsers import expat 29 30D = os.path.dirname(os.path.abspath(__file__)) 31OF = "urn:oasis:names:tc:opendocument:xmlns:of:1.2" 32NS = "urn:oasis:names:tc:opendocument:xmlns:%s:1.0" 33ATTRS = {NS % "style" + " condition": "style:condition", NS % "table" + " condition": "table:condition", 34 NS % "table" + " expression": "table:expression", NS % "table" + " formula": "table:formula", 35 NS % "text" + " formula": "text:formula"} 36SPREADSHEET = NS % "office" + " spreadsheet" 37STANDARD = {l.strip().upper() for l in open(os.path.join(D, "openformula-functions.txt")) if l.strip() and not l.startswith("#")} 38 39 40class Bad(Exception): 41 def __init__(self, pos, msg): 42 Exception.__init__(self, msg) 43 self.pos, self.msg = pos, msg 44 45 46def is_letter(c): 47 return unicodedata.category(c)[0] == "L" or unicodedata.category(c) == "Nl" 48 49 50def is_namechar(c): 51 return is_letter(c) or unicodedata.category(c) in ("Nd", "Mn", "Mc", "Me") or c == "_" 52 53 54# Part 2 5.3, 5.4, 5.8, 5.12 55NUMBER = re.compile(r"(?:[0-9]+(?:\.[0-9]+)?|\.[0-9]+)(?:[eE][-+]?[0-9]+)?") 56STRING = re.compile(r'"(?:[^"\x00]|"")*"') 57SINGLE = re.compile(r"'(?:[^']|'')+'") 58ERROR = re.compile(r"#[A-Z0-9]+(?:[!?]|/(?:[A-Z]|[0-9][!?]))") 59_Q = r"\$?'(?:[^']|'')+'" 60_SN = r"(?:%s|\$?[^\]\. #$']+)" % _Q 61_COL, _ROW = r"\$?[A-Z]+", r"\$?[1-9][0-9]*" 62_CELL = _COL + _ROW 63_SL = r"%s(?:\.(?:%s|%s))*" % (_SN, _CELL, _Q) 64RANGE = re.compile("|".join([ 65 r"(?:%s)?\.%s(?::\.%s)?" % (_SL, _CELL, _CELL), r"(?:%s)?\.%s:\.%s" % (_SL, _COL, _COL), r"(?:%s)?\.%s:\.%s" % (_SL, _ROW, _ROW), 66 r"%s\.%s:%s\.%s" % (_SL, _CELL, _SL, _CELL), r"%s\.%s:%s\.%s" % (_SL, _COL, _SL, _COL), r"%s\.%s:%s\.%s" % (_SL, _ROW, _SL, _ROW)])) 67QSHEET = re.compile(_Q) 68CELLREF = re.compile(r"[A-Za-z]+[0-9]+") 69INFIX = ("<>", "<=", ">=", "+", "-", "*", "/", "^", "=", "<", ">", "&", ":", "!", "~") 70# Part 1 19.468, 19.596 71DECIMAL = re.compile(r"[-+]?(?:[0-9]+(?:\.[0-9]*)?|\.[0-9]+)") 72RELOP = re.compile(r"<=|>=|!=|<|>|=") 73CNAME = re.compile(r"[a-z][a-z-]*") 74 75 76def check_iri(iri): 77 """Approximates the RFC 3987 IRI-reference rule: no controls, spaces or the characters excluded from IRIs.""" 78 if re.search(r'[\x00-\x20<>"{}|\\^`\x7f]', iri) or re.search(r"%(?![0-9A-Fa-f]{2})", iri): 79 raise ValueError("not an IRI reference") 80 81 82class Parser: 83 def __init__(self, text): 84 self.s, self.i, self.funcs, self.ragged = text, 0, [], None 85 86 def fail(self, msg, at=None): 87 raise Bad(self.i if at is None else at, msg) 88 89 def at(self, chars): 90 return self.i < len(self.s) and self.s[self.i] in chars 91 92 def ws(self): 93 while self.at(" \t\n\r"): 94 self.i += 1 95 96 def expect(self, ch): 97 if not self.at(ch): 98 self.fail("%r expected" % ch) 99 self.i += 1 100 101 def end(self): 102 if self.i < len(self.s): 103 self.fail("unexpected %r" % self.s[self.i]) 104 105 # 5.2: Formula ::= Intro? Expression 106 def formula(self): 107 if self.at("="): 108 self.i += 1 109 if self.at("="): 110 self.i += 1 111 self.expression() 112 self.end() 113 114 def expression(self): 115 self.ws() 116 self.operand() 117 while True: 118 self.ws() 119 op = next((o for o in INFIX if self.s.startswith(o, self.i)), None) 120 if op is None: 121 return 122 self.i += len(op) 123 self.ws() 124 self.operand() 125 126 def operand(self): 127 while self.at("+-"): 128 self.i += 1 129 self.ws() 130 self.primary() 131 while True: 132 j = self.i 133 self.ws() 134 if self.at("%"): 135 self.i += 1 136 else: 137 self.i = j 138 return 139 140 def primary(self): 141 s, i = self.s, self.i 142 if i >= len(s): 143 self.fail("expression expected") 144 c = s[i] 145 m = NUMBER.match(s, i) if (c in "0123456789.") else None 146 if m: 147 self.i = m.end() 148 elif c == '"': 149 m = STRING.match(s, i) 150 if not m: 151 self.fail("unterminated string") 152 self.i = m.end() 153 elif c == "{": 154 self.array() 155 elif c == "(": 156 self.i += 1 157 self.expression() 158 self.expect(")") 159 elif c == "[": 160 self.reference() 161 elif c == "#": 162 m = ERROR.match(s, i) 163 if not m: 164 self.fail("malformed error constant") 165 self.i = m.end() 166 elif c in "'$": 167 self.quoted_or_named() 168 elif is_letter(c): 169 self.name() 170 else: 171 self.fail("unexpected %r" % c) 172 173 def array(self): 174 self.i += 1 175 widths = [] 176 while True: 177 n = 1 178 self.expression() 179 while self.at(";"): 180 self.i += 1 181 self.expression() 182 n += 1 183 widths.append(n) 184 if self.at("|"): 185 self.i += 1 186 continue 187 break 188 self.expect("}") 189 if len(set(widths)) > 1: 190 self.ragged = widths 191 192 def name(self): 193 s, j = self.s, self.i 194 k = j 195 while k < len(s) and (is_namechar(s[k]) or s[k] == "."): 196 k += 1 197 if k < len(s) and s[k] == "(": 198 self.funcs.append(s[j:k]) 199 self.i = k + 1 200 self.params() 201 return 202 ident = s[j:k].split(".", 1)[0] 203 self.i = j + len(ident) 204 if self.i == k and re.match(r"[ \t\n\r]+\(", s[k:]): 205 self.fail("whitespace between function name and '('") 206 self.check_identifier(ident) 207 208 def check_identifier(self, ident): 209 if CELLREF.fullmatch(ident): 210 self.fail("%r looks like a cell reference; references are written in square brackets" % ident, self.i - len(ident)) 211 if ident.lower() in ("true", "false"): 212 self.fail("%r is not an identifier; use %s()" % (ident, ident.upper()), self.i - len(ident)) 213 214 def params(self): 215 while True: 216 self.ws() 217 if self.at(");"): 218 pass 219 else: 220 self.expression() 221 self.ws() 222 if self.at(";"): 223 self.i += 1 224 continue 225 self.expect(")") 226 return 227 228 # 5.8, 5.10, 5.11 229 def source(self): 230 """Source ::= "'" IRI "'" "#" at the current position, if there is one.""" 231 m = SINGLE.match(self.s, self.i) 232 if m and self.s.startswith("#", m.end()): 233 try: 234 check_iri(m.group(0)[1:-1].replace("''", "'")) 235 except ValueError as e: 236 self.fail("source: %s" % e) 237 self.i = m.end() + 1 238 return True 239 return False 240 241 def simple_named(self): 242 """SimpleNamedExpression ::= Identifier | '$$' (Identifier | SingleQuoted)""" 243 if self.s.startswith("$$", self.i): 244 self.i += 2 245 m = SINGLE.match(self.s, self.i) 246 if m: 247 self.i = m.end() 248 return 249 self.identifier() 250 251 def quoted_or_named(self): 252 s = self.s 253 if self.source(): 254 m = QSHEET.match(s, self.i) 255 if m and s.startswith(".", m.end()): 256 self.i = m.end() + 1 257 self.simple_named() 258 return 259 if s.startswith("$$", self.i): 260 self.simple_named() 261 return 262 m = QSHEET.match(s, self.i) 263 if not m: 264 self.fail("'$' must be '$$' or precede a quoted sheet name") 265 j = m.end() 266 k = j 267 while k < len(s) and s[k] in " \t\n\r": 268 k += 1 269 if s.startswith(".", j): 270 self.i = j + 1 271 self.simple_named() 272 elif s[self.i] != "$" and s.startswith("!!", k): 273 self.i = k + 2 274 self.ws() 275 m = SINGLE.match(s, self.i) 276 if not m: 277 self.fail("quoted label expected after '!!'") 278 self.i = m.end() 279 elif s[self.i] == "$": 280 self.fail("a quoted sheet name must be followed by '.'") 281 else: 282 self.i = j 283 284 def identifier(self): 285 s, j = self.s, self.i 286 if j >= len(s) or not is_letter(s[j]): 287 self.fail("identifier expected") 288 k = j 289 while k < len(s) and is_namechar(s[k]): 290 k += 1 291 self.i = k 292 self.check_identifier(s[j:k]) 293 294 def reference(self): 295 s = self.s 296 j = self.i + 1 297 k = j 298 while k < len(s) and s[k] != "]": 299 if s[k] == "'": 300 m = SINGLE.match(s, k) 301 if not m: 302 self.fail("unterminated quote in reference") 303 k = m.end() 304 else: 305 k += 1 306 if k >= len(s): 307 self.fail("reference without ']'", self.i) 308 inner = s[j:k] 309 sub = Parser(inner) 310 sub.i = 0 311 try: 312 if inner == "#REF!": 313 pass 314 else: 315 sub.source() 316 if not RANGE.fullmatch(inner, sub.i): 317 raise Bad(j + sub.i, "malformed reference [%s]" % inner) 318 except Bad as e: 319 raise Bad(j + e.pos if e.pos < len(inner) else j, e.msg) 320 self.i = k + 1 321 322 # Part 1 19.468 / 19.596 value, condition 323 def value(self): 324 s, save = self.s, self.i 325 for rx in (DECIMAL, STRING): 326 m = rx.match(s, save) 327 if m: 328 j = m.end() 329 while j < len(s) and s[j] in " \t\n\r": 330 j += 1 331 if j >= len(s) or s[j] in ",)": 332 self.i = j 333 return 334 self.i = save 335 self.expression() 336 337 def cname(self): 338 self.ws() 339 m = CNAME.match(self.s, self.i) 340 if not m: 341 self.fail("condition expected") 342 self.i = m.end() 343 return m.group(0) 344 345 def call(self, nargs): 346 """'(' value {',' value} ')' or '()'""" 347 self.expect("(") 348 self.ws() 349 if nargs == 0: 350 self.expect(")") 351 return 352 for n in range(nargs): 353 if n: 354 self.ws() 355 self.expect(",") 356 self.ws() 357 self.value() 358 self.ws() 359 self.expect(")") 360 361 def op_value(self): 362 self.ws() 363 if not RELOP.match(self.s, self.i): 364 self.fail("relational operator expected") 365 self.i = RELOP.match(self.s, self.i).end() 366 self.ws() 367 self.value() 368 369 def style_condition(self): 370 name = self.cname() 371 if name in ("footnote", "endnote", "header", "footer", "section", "table", "table-header"): 372 self.call(0) 373 elif name in ("list-level", "outline-level"): 374 self.call(0) 375 self.ws() 376 self.expect("=") 377 self.ws() 378 m = re.compile(r"\+?0*[1-9][0-9]*").match(self.s, self.i) 379 if not m: 380 self.fail("positive integer expected") 381 self.i = m.end() 382 elif name == "value": 383 self.call(0) 384 self.ws() 385 m = RELOP.match(self.s, self.i) 386 if not m: 387 self.fail("relational operator expected") 388 self.i = m.end() 389 self.ws() 390 m = re.compile(r"true|false").match(self.s, self.i) or DECIMAL.match(self.s, self.i) 391 if not m: 392 self.fail("number, true or false expected") 393 self.i = m.end() 394 elif name == "cell-content": 395 self.call(0) 396 self.op_value() 397 elif name in ("cell-content-is-between", "cell-content-is-not-between"): 398 self.call(2) 399 elif name == "is-true-formula": 400 self.call_expression() 401 else: 402 self.fail("unknown condition %r" % name, self.i - len(name)) 403 self.ws() 404 self.end() 405 406 def call_expression(self): 407 self.expect("(") 408 self.expression() 409 self.expect(")") 410 411 def value_condition(self): 412 name = self.cname() 413 if name == "cell-content": 414 self.call(0) 415 self.op_value() 416 elif name in ("cell-content-is-between", "cell-content-is-not-between"): 417 self.call(2) 418 elif name == "is-true-formula": 419 self.call_expression() 420 else: 421 self.fail("value condition expected, found %r" % name, self.i - len(name)) 422 423 def string_list(self): 424 """list of string entries separated by ';'; leaves the position before ')'""" 425 s, j = self.s, self.i 426 while True: 427 m = STRING.match(s, j) 428 if not m: 429 return False 430 k = m.end() 431 while k < len(s) and s[k] in " \t\n\r": 432 k += 1 433 if s.startswith(";", k): 434 j = k + 1 435 while j < len(s) and s[j] in " \t\n\r": 436 j += 1 437 elif s.startswith(")", k): 438 self.i = k 439 return True 440 else: 441 return False 442 443 def validation_condition(self): 444 name = self.cname() 445 if name == "cell-content-text-length": 446 self.call(0) 447 self.op_value() 448 elif name in ("cell-content-text-length-is-between", "cell-content-text-length-is-not-between"): 449 self.call(2) 450 elif name == "cell-content-is-in-list": 451 self.expect("(") 452 self.ws() 453 if not self.string_list(): 454 self.expression() 455 self.expect(")") 456 elif name in ("cell-content-is-decimal-number", "cell-content-is-whole-number", "cell-content-is-date", "cell-content-is-time"): 457 self.call(0) 458 m = re.compile(r"\s+and\s+").match(self.s, self.i) 459 if not m: 460 self.fail("'and' expected") 461 self.i = m.end() 462 self.value_condition() 463 elif name == "is-true-formula": 464 self.call_expression() 465 else: 466 self.fail("unknown condition %r" % name, self.i - len(name)) 467 self.ws() 468 self.end() 469 470 471def check_value(attr, body, has_prefix): 472 """Returns (None | (pos, message), [function names], ragged column counts | None).""" 473 p = Parser(body) 474 try: 475 if attr in ("table:formula", "text:formula"): 476 p.formula() 477 elif attr == "table:expression": 478 if has_prefix and not body.startswith("="): 479 raise Bad(0, "an expression with a namespace prefix must start with '=' (19.635)") 480 p.formula() 481 elif attr == "style:condition": 482 p.style_condition() 483 else: 484 p.validation_condition() 485 except Bad as e: 486 return (e.pos, e.msg), p.funcs, p.ragged 487 return None, p.funcs, p.ragged 488 489 490NCPREFIX = re.compile(r"([^\W\d][\w.\-]*):") 491 492 493def check_stream(data, stats): 494 """Returns [(line, col, level, rule, message)].""" 495 out = [] 496 scope = collections.defaultdict(list) 497 state = {"depth": 0, "ss": None} 498 p = expat.ParserCreate(namespace_separator=" ") 499 p.StartNamespaceDeclHandler = lambda pre, uri: scope[pre].append(uri) 500 p.EndNamespaceDeclHandler = lambda pre: scope[pre].pop() 501 502 def start(name, attrs): 503 state["depth"] += 1 504 if name == SPREADSHEET: 505 state["ss"] = state["depth"] 506 for key, value in attrs.items(): 507 attr = ATTRS.get(key) 508 if attr is None: 509 continue 510 line, col = p.CurrentLineNumber, p.CurrentColumnNumber 511 512 def add(level, rule, msg): 513 out.append((line, col, level, rule, '%s="%s": %s' % (attr, value if len(value) < 80 else value[:77] + "...", msg))) 514 m = NCPREFIX.match(value) 515 body, has_prefix = value, False 516 if m: 517 pre = m.group(1) 518 uri = scope[pre][-1] if scope.get(pre) else None 519 stats[(attr, pre if uri is None else uri)] += 1 520 if uri is None: 521 add("shall", "formula-prefix-unbound", "namespace prefix \"%s\" is not bound" % pre) 522 continue 523 if uri != OF: 524 if attr == "table:formula" and state["ss"] is not None: 525 add("shall", "formula-namespace", "bound to <%s>, not to the of:1.2 namespace (2.2.4 D)" % uri) 526 else: 527 add("should", "formula-foreign-namespace", "bound to <%s>; the syntax is not defined by Part 2" % uri) 528 continue 529 body, has_prefix = value[m.end():], True 530 else: 531 stats[(attr, "(none)")] += 1 532 err, funcs, ragged = check_value(attr, body, has_prefix) 533 if err: 534 pos, msg = err 535 add("shall", "formula-syntax", "%s at character %d" % (msg, pos + (len(value) - len(body)) + 1)) 536 if ragged: 537 add("should", "formula-array-ragged", "inline array rows have %s columns (5.13)" % "/".join(map(str, ragged))) 538 for f in funcs: 539 if f.upper() not in STANDARD and "." not in f: 540 add("should", "formula-function-unprefixed", "%s is not a function of Part 2 and has no origin prefix (5.7)" % f) 541 if f != f.upper(): 542 add("should", "formula-function-case", "%s: function names should be written in upper case (6.1)" % f) 543 p.StartElementHandler = start 544 545 def end(name): 546 if state["ss"] == state["depth"]: 547 state["ss"] = None 548 state["depth"] -= 1 549 p.EndElementHandler = end 550 try: 551 p.Parse(data, True) 552 except expat.ExpatError as e: 553 out.append((e.lineno, e.offset, "shall", "formula-stream", "not namespace-well-formed: " + expat.ErrorString(e.code))) 554 return out 555 556 557def main(): 558 outdir, fjson = sys.argv[1], sys.argv[2] 559 if not os.path.abspath(fjson).startswith(os.path.join(D, "runs") + os.sep): 560 sys.exit("formulacheck.py: <formulas.json> must live under " + os.path.join(D, "runs")) 561 errors, bad, stats = [], [], collections.Counter() 562 pkgs = sorted(p for p in os.listdir(outdir) if not p.startswith(".")) 563 for pkg in pkgs: 564 try: 565 z = zipfile.ZipFile(os.path.join(outdir, pkg)) 566 except Exception: 567 bad.append(pkg); continue 568 for name in z.namelist(): 569 if name.rsplit("/", 1)[-1] not in ("content.xml", "styles.xml", "settings.xml"): 570 continue 571 for line, col, level, rule, msg in check_stream(z.read(name), stats): 572 errors.append([pkg + "/" + name, line, col, "%s: [%s] %s" % (level, rule, msg)]) 573 json.dump({"packages": pkgs, "bad": bad, "checked": {"%s %s" % k: v for k, v in sorted(stats.items())}, "errors": errors}, open(fjson, "w")) 574 shall = [e for e in errors if e[3].startswith("shall:")] 575 print(f"formula check: {sum(stats.values())} values checked; {len(shall)} shall and {len(errors) - len(shall)} should findings in " 576 f"{len({e[0].split('/')[0] for e in errors})} of {len(pkgs)} packages, unreadable: {bad}") 577 for (attr, ns), v in sorted(stats.items()): 578 print(f" {v:6d} {attr} {ns}") 579 rules = collections.Counter(e[3].split("]")[0] + "]" for e in errors) 580 for k, v in sorted(rules.items()): 581 print(f" {v:6d} {k}") 582 583 584if __name__ == "__main__": 585 main() 586