Coverage for python/lsst/daf/butler/registry/queries/expressions/normalForm.py: 44%

1# This file is part of daf_butler. 

2# 

3# Developed for the LSST Data Management System. 

4# This product includes software developed by the LSST Project 

5# (https://www.lsst.org). 

6# See the COPYRIGHT file at the top-level directory of this distribution 

7# for details of code ownership. 

8# 

9# This software is dual licensed under the GNU General Public License and also 

10# under a 3-clause BSD license. Recipients may choose which of these licenses 

11# to use; please see the files gpl-3.0.txt and/or bsd_license.txt, 

12# respectively. If you choose the GPL option then the following text applies 

13# (but note that there is still no warranty even if you opt for BSD instead): 

14# 

15# This program is free software: you can redistribute it and/or modify 

16# it under the terms of the GNU General Public License as published by 

17# the Free Software Foundation, either version 3 of the License, or 

18# (at your option) any later version. 

19# 

20# This program is distributed in the hope that it will be useful, 

21# but WITHOUT ANY WARRANTY; without even the implied warranty of 

22# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 

23# GNU General Public License for more details. 

24# 

25# You should have received a copy of the GNU General Public License 

26# along with this program. If not, see <https://www.gnu.org/licenses/>. 

27 

28from __future__ import annotations 

29 

30__all__ = ( 

31 "NormalForm", 

32 "NormalFormExpression", 

33 "NormalFormVisitor", 

34) 

35 

36import enum 

37from abc import ABC, abstractmethod 

38from collections.abc import Iterator, Sequence 

39from typing import Generic, TypeVar 

40from uuid import UUID 

41 

42import astropy.time 

43 

44from .parser import BinaryOp, Node, Parens, TreeVisitor, UnaryOp 

45 

46 

47class LogicalBinaryOperator(enum.Enum): 

48 """Enumeration for logical binary operators. 

49 

50 These intentionally have the same names (including capitalization) as the 

51 string binary operators used in the parser itself. Boolean values are 

52 used to enable generic code that works on either operator (particularly 

53 ``LogicalBinaryOperator(not self)`` as a way to get the other operator). 

54 

55 Which is `True` and which is `False` is just a convention, but one shared 

56 by `LogicalBinaryOperator` and `NormalForm`. 

57 """ 

58 

59 AND = True 

60 OR = False 

61 

62 def apply(self, lhs: TransformationWrapper, rhs: TransformationWrapper) -> LogicalBinaryOperation: 

63 """Return a `TransformationWrapper` object representing this operator 

64 applied to the given operands. 

65 

66 This is simply syntactic sugar for the `LogicalBinaryOperation` 

67 constructor. 

68 

69 Parameters 

70 ---------- 

71 lhs : `TransformationWrapper` 

72 First operand. 

73 rhs : `TransformationWrapper` 

74 Second operand. 

75 

76 Returns 

77 ------- 

78 operation : `LogicalBinaryOperation` 

79 Object representing the operation. 

80 """ 

81 return LogicalBinaryOperation(lhs, self, rhs) 

82 

83 

84class NormalForm(enum.Enum): 

85 """Enumeration for boolean normal forms. 

86 

87 Both normal forms require all NOT operands to be moved "inside" any AND 

88 or OR operations (i.e. by applying DeMorgan's laws), with either all AND 

89 operations or all OR operations appearing outside the other (`CONJUNCTIVE`, 

90 and `DISJUNCTIVE`, respectively). 

91 

92 Boolean values are used here to enable generic code that works on either 

93 form, and for interoperability with `LogicalBinaryOperator`. 

94 

95 Which is `True` and which is `False` is just a convention, but one shared 

96 by `LogicalBinaryOperator` and `NormalForm`. 

97 """ 

98 

99 CONJUNCTIVE = True 

100 """Form in which AND operations may have OR operands, but not the reverse. 

101 

102 For example, ``A AND (B OR C)`` is in conjunctive normal form, but 

103 ``A OR (B AND C)`` and ``A AND (B OR (C AND D))`` are not. 

104 """ 

105 

106 DISJUNCTIVE = False 

107 """Form in which OR operations may have AND operands, but not the reverse. 

108 

109 For example, ``A OR (B AND C)`` is in disjunctive normal form, but 

110 ``A AND (B OR C)`` and ``A OR (B AND (C OR D))`` are not. 

111 """ 

112 

113 @property 

114 def inner(self) -> LogicalBinaryOperator: 

115 """The operator that is not permitted to contain operations of the 

116 other type in this form. 

117 

118 Note that this operation may still appear as the outermost operator in 

119 an expression in this form if there are no operations of the other 

120 type. 

121 """ 

122 return LogicalBinaryOperator(not self.value) 

123 

124 @property 

125 def outer(self) -> LogicalBinaryOperator: 

126 """The operator that is not permitted to be contained by operations of 

127 the other type in this form. 

128 

129 Note that an operation of this type is not necessarily the outermost 

130 operator in an expression in this form; the expression need not contain 

131 any operations of this type. 

132 """ 

133 return LogicalBinaryOperator(self.value) 

134 

135 def allows(self, *, inner: LogicalBinaryOperator, outer: LogicalBinaryOperator) -> bool: 

136 """Test whether this form allows the given operator relationships. 

137 

138 Parameters 

139 ---------- 

140 inner : `LogicalBinaryOperator` 

141 Inner operator in an expression. May be the same as ``outer``. 

142 outer : `LogicalBinaryOperator` 

143 Outer operator in an expression. May be the same as ``inner``. 

144 

145 Returns 

146 ------- 

147 allowed : `bool` 

148 Whether this operation relationship is allowed. 

149 """ 

150 return inner == outer or outer is self.outer 

151 

152 

153_T = TypeVar("_T") 

154_U = TypeVar("_U") 

155_V = TypeVar("_V") 

156 

157 

158class NormalFormVisitor(Generic[_T, _U, _V]): 

159 """A visitor interface for `NormalFormExpression`. 

160 

161 A visitor implementation may inherit from both `NormalFormVisitor` and 

162 `TreeVisitor` and implement `visitBranch` as ``node.visit(self)`` to 

163 visit each node of the entire tree (or similarly with composition, etc). 

164 In this case, `TreeVisitor.visitBinaryOp` will never be called with a 

165 logical OR or AND operation, because these will all have been moved into 

166 calls to `visitInner` and `visitOuter` instead. 

167 

168 See also `NormalFormExpression.visit`. 

169 """ 

170 

171 @abstractmethod 

172 def visitBranch(self, node: Node) -> _T: 

173 """Visit a regular `Node` and its child nodes. 

174 

175 Parameters 

176 ---------- 

177 node : `Node` 

178 A branch of the expression tree that contains no AND or OR 

179 operations. 

180 

181 Returns 

182 ------- 

183 result 

184 Implementation-defined result to be gathered and passed to 

185 `visitInner`. 

186 """ 

187 raise NotImplementedError() 

188 

189 @abstractmethod 

190 def visitInner(self, branches: Sequence[_T], form: NormalForm) -> _U: 

191 """Visit a sequence of inner OR (for `~NormalForm.CONJUNCTIVE` form) 

192 or AND (for `~NormalForm.DISJUNCTIVE`) operands. 

193 

194 Parameters 

195 ---------- 

196 branches : `~collections.abc.Sequence` 

197 Sequence of tuples, where the first element in each tuple is the 

198 result of a call to `visitBranch`, and the second is the `Node` on 

199 which `visitBranch` was called. 

200 form : `NormalForm` 

201 Form this expression is in. ``form.inner`` is the operator that 

202 joins the operands in ``branches``. 

203 

204 Returns 

205 ------- 

206 result 

207 Implementation-defined result to be gathered and passed to 

208 `visitOuter`. 

209 """ 

210 raise NotImplementedError() 

211 

212 @abstractmethod 

213 def visitOuter(self, branches: Sequence[_U], form: NormalForm) -> _V: 

214 """Visit the sequence of outer AND (for `~NormalForm.CONJUNCTIVE` form) 

215 or OR (for `~NormalForm.DISJUNCTIVE`) operands. 

216 

217 Parameters 

218 ---------- 

219 branches : `~collections.abc.Sequence` 

220 Sequence of return values from calls to `visitInner`. 

221 form : `NormalForm` 

222 Form this expression is in. ``form.outer`` is the operator that 

223 joins the operands in ``branches``. 

224 

225 Returns 

226 ------- 

227 result 

228 Implementation-defined result to be returned by 

229 `NormalFormExpression.visitNormalForm`. 

230 """ 

231 raise NotImplementedError() 

232 

233 

234class NormalFormExpression: 

235 """A boolean expression in a standard normal form. 

236 

237 Most code should use `fromTree` to construct new instances instead of 

238 calling the constructor directly. See `NormalForm` for a description of 

239 the two forms. 

240 

241 Parameters 

242 ---------- 

243 nodes : `~collections.abc.Sequence` [ `~collections.abc.Sequence` \ 

244 [ `Node` ] ] 

245 Non-AND, non-OR branches of three tree, with the AND and OR operations 

246 combining them represented by position in the nested sequence - the 

247 inner sequence is combined via ``form.inner``, and the outer sequence 

248 combines those via ``form.outer``. 

249 form : `NormalForm` 

250 Enumeration value indicating the form this expression is in. 

251 """ 

252 

253 def __init__(self, nodes: Sequence[Sequence[Node]], form: NormalForm): 

254 self._form = form 

255 self._nodes = nodes 

256 

257 def __str__(self) -> str: 

258 return str(self.toTree()) 

259 

260 @staticmethod 

261 def fromTree(root: Node, form: NormalForm) -> NormalFormExpression: 

262 """Construct a `NormalFormExpression` by normalizing an arbitrary 

263 expression tree. 

264 

265 Parameters 

266 ---------- 

267 root : `Node` 

268 Root of the tree to be normalized. 

269 form : `NormalForm` 

270 Enumeration value indicating the form to normalize to. 

271 

272 Notes 

273 ----- 

274 Converting an arbitrary boolean expression to either normal form is an 

275 NP-hard problem, and this is a brute-force algorithm. I'm not sure 

276 what its actual algorithmic scaling is, but it'd definitely be a bad 

277 idea to attempt to normalize an expression with hundreds or thousands 

278 of clauses. 

279 """ 

280 wrapper = root.visit(TransformationVisitor()).normalize(form) 

281 nodes = [] 

282 for outerOperands in wrapper.flatten(form.outer): 

283 nodes.append([w.unwrap() for w in outerOperands.flatten(form.inner)]) 

284 return NormalFormExpression(nodes, form=form) 

285 

286 @property 

287 def form(self) -> NormalForm: 

288 """Enumeration value indicating the form this expression is in.""" 

289 return self._form 

290 

291 def visit(self, visitor: NormalFormVisitor[_T, _U, _V]) -> _V: 

292 """Apply a visitor to the expression, explicitly taking advantage of 

293 the special structure guaranteed by the normal forms. 

294 

295 Parameters 

296 ---------- 

297 visitor : `NormalFormVisitor` 

298 Visitor object to apply. 

299 

300 Returns 

301 ------- 

302 result 

303 Return value from calling ``visitor.visitOuter`` after visiting 

304 all other nodes. 

305 """ 

306 visitedOuterBranches: list[_U] = [] 

307 for nodeInnerBranches in self._nodes: 

308 visitedInnerBranches = [visitor.visitBranch(node) for node in nodeInnerBranches] 

309 visitedOuterBranches.append(visitor.visitInner(visitedInnerBranches, self.form)) 

310 return visitor.visitOuter(visitedOuterBranches, self.form) 

311 

312 def toTree(self) -> Node: 

313 """Convert ``self`` back into an equivalent tree, preserving the 

314 form of the boolean expression but representing it in memory as 

315 a tree. 

316 

317 Returns 

318 ------- 

319 tree : `Node` 

320 Root of the tree equivalent to ``self``. 

321 """ 

322 visitor = TreeReconstructionVisitor() 

323 return self.visit(visitor) 

324 

325 

326class PrecedenceTier(enum.Enum): 

327 """An enumeration used to track operator precedence. 

328 

329 This enum is currently used only to inject parentheses into boolean 

330 logic that has been manipulated into a new form, and because those 

331 parentheses are only used for stringification, the goal here is human 

332 readability, not precision. 

333 

334 Lower enum values represent tighter binding, but code deciding whether to 

335 inject parentheses should always call `needsParens` instead of comparing 

336 values directly. 

337 """ 

338 

339 TOKEN = 0 

340 """Precedence tier for literals, identifiers, and expressions already in 

341 parentheses. 

342 """ 

343 

344 UNARY = 1 

345 """Precedence tier for unary operators, which always bind more tightly 

346 than any binary operator. 

347 """ 

348 

349 VALUE_BINARY_OP = 2 

350 """Precedence tier for binary operators that return non-boolean values. 

351 """ 

352 

353 COMPARISON = 3 

354 """Precedence tier for binary comparison operators that accept non-boolean 

355 values and return boolean values. 

356 """ 

357 

358 AND = 4 

359 """Precedence tier for logical AND. 

360 """ 

361 

362 OR = 5 

363 """Precedence tier for logical OR. 

364 """ 

365 

366 @classmethod 

367 def needsParens(cls, outer: PrecedenceTier, inner: PrecedenceTier) -> bool: 

368 """Test whether parentheses should be added around an operand. 

369 

370 Parameters 

371 ---------- 

372 outer : `PrecedenceTier` 

373 Precedence tier for the operation. 

374 inner : `PrecedenceTier` 

375 Precedence tier for the operand. 

376 

377 Returns 

378 ------- 

379 needed : `bool` 

380 If `True`, parentheses should be added. 

381 

382 Notes 

383 ----- 

384 This method special cases logical binary operators for readability, 

385 adding parentheses around ANDs embedded in ORs, and avoiding them in 

386 chains of the same operator. If it is ever actually used with other 

387 binary operators as ``outer``, those would probably merit similar 

388 attention (or a totally new approach); its current approach would 

389 aggressively add a lot of unfortunate parentheses because (aside from 

390 this special-casing) it doesn't know about commutativity. 

391 

392 In fact, this method is rarely actually used for logical binary 

393 operators either; the `LogicalBinaryOperation.unwrap` method that calls 

394 it is never invoked by `NormalFormExpression` (the main public 

395 interface), because those operators are flattened out (see 

396 `TransformationWrapper.flatten`) instead. Parentheses are instead 

397 added there by `TreeReconstructionVisitor`, which is simpler because 

398 the structure of operators is restricted. 

399 """ 

400 if outer is cls.OR and inner is cls.AND: 

401 return True 

402 if outer is cls.OR and inner is cls.OR: 

403 return False 

404 if outer is cls.AND and inner is cls.AND: 

405 return False 

406 return outer.value <= inner.value 

407 

408 

409BINARY_OPERATOR_PRECEDENCE = { 

410 "=": PrecedenceTier.COMPARISON, 

411 "!=": PrecedenceTier.COMPARISON, 

412 "<": PrecedenceTier.COMPARISON, 

413 "<=": PrecedenceTier.COMPARISON, 

414 ">": PrecedenceTier.COMPARISON, 

415 ">=": PrecedenceTier.COMPARISON, 

416 "OVERLAPS": PrecedenceTier.COMPARISON, 

417 "+": PrecedenceTier.VALUE_BINARY_OP, 

418 "-": PrecedenceTier.VALUE_BINARY_OP, 

419 "*": PrecedenceTier.VALUE_BINARY_OP, 

420 "/": PrecedenceTier.VALUE_BINARY_OP, 

421 "AND": PrecedenceTier.AND, 

422 "OR": PrecedenceTier.OR, 

423} 

424 

425 

426class TransformationWrapper(ABC): 

427 """A base class for `Node` wrappers that can be used to transform boolean 

428 operator expressions. 

429 

430 Notes 

431 ----- 

432 `TransformationWrapper` instances should only be directly constructed by 

433 each other or `TransformationVisitor`. No new subclasses beyond those in 

434 this module should be added. 

435 

436 While `TransformationWrapper` and its subclasses contain the machinery 

437 for transforming expressions to normal forms, it does not provide a 

438 convenient interface for working with expressions in those forms; most code 

439 should just use `NormalFormExpression` (which delegates to 

440 `TransformationWrapper` internally) instead. 

441 """ 

442 

443 __slots__ = () 

444 

445 @abstractmethod 

446 def __str__(self) -> str: 

447 raise NotImplementedError() 

448 

449 @property 

450 @abstractmethod 

451 def precedence(self) -> PrecedenceTier: 

452 """Return the precedence tier for this node (`PrecedenceTier`). 

453 

454 Notes 

455 ----- 

456 This is only used when reconstructing a full `Node` tree in `unwrap` 

457 implementations, and only to inject parenthesis that are necessary for 

458 correct stringification but nothing else (because the tree structure 

459 itself embeds the correct order of operations already). 

460 """ 

461 raise NotImplementedError() 

462 

463 @abstractmethod 

464 def not_(self) -> TransformationWrapper: 

465 """Return a wrapper that represents the logical NOT of ``self``. 

466 

467 Returns 

468 ------- 

469 wrapper : `TransformationWrapper` 

470 A wrapper that represents the logical NOT of ``self``. 

471 """ 

472 raise NotImplementedError() 

473 

474 def satisfies(self, form: NormalForm) -> bool: 

475 """Test whether this expressions is already in a normal form. 

476 

477 The default implementation is appropriate for "atomic" classes that 

478 never contain any AND or OR operations at all. 

479 

480 Parameters 

481 ---------- 

482 form : `NormalForm` 

483 Enumeration indicating the form to test for. 

484 

485 Returns 

486 ------- 

487 satisfies : `bool` 

488 Whether ``self`` satisfies the requirements of ``form``. 

489 """ 

490 return True 

491 

492 def normalize(self, form: NormalForm) -> TransformationWrapper: 

493 """Return an expression equivalent to ``self`` in a normal form. 

494 

495 The default implementation is appropriate for "atomic" classes that 

496 never contain any AND or OR operations at all. 

497 

498 Parameters 

499 ---------- 

500 form : `NormalForm` 

501 Enumeration indicating the form to convert to. 

502 

503 Returns 

504 ------- 

505 normalized : `TransformationWrapper` 

506 An expression equivalent to ``self`` for which 

507 ``normalized.satisfies(form)`` returns `True`. 

508 

509 Notes 

510 ----- 

511 Converting an arbitrary boolean expression to either normal form is an 

512 NP-hard problem, and this is a brute-force algorithm. I'm not sure 

513 what its actual algorithmic scaling is, but it'd definitely be a bad 

514 idea to attempt to normalize an expression with hundreds or thousands 

515 of clauses. 

516 """ 

517 return self 

518 

519 def flatten(self, operator: LogicalBinaryOperator) -> Iterator[TransformationWrapper]: 

520 """Recursively flatten the operands of any nested operators of the 

521 given type. 

522 

523 For an expression like ``(A AND ((B OR C) AND D)`` (with 

524 ``operator == AND``), `flatten` yields ``A, (B OR C), D``. 

525 

526 The default implementation is appropriate for "atomic" classes that 

527 never contain any AND or OR operations at all. 

528 

529 Parameters 

530 ---------- 

531 operator : `LogicalBinaryOperator` 

532 Operator whose operands to flatten. 

533 

534 Yields 

535 ------ 

536 operands : `~collections.abc.Iterator` [ `TransformationWrapper` ] 

537 Operands that, if combined with ``operator``, yield an expression 

538 equivalent to ``self``. 

539 """ 

540 yield self 

541 

542 def _satisfiesDispatch( 

543 self, operator: LogicalBinaryOperator, other: TransformationWrapper, *, form: NormalForm 

544 ) -> bool: 

545 """Test whether ``operator.apply(self, other)`` is in a normal form. 

546 

547 The default implementation is appropriate for classes that never 

548 contain any AND or OR operations at all. 

549 

550 Parameters 

551 ---------- 

552 operator : `LogicalBinaryOperator` 

553 Operator for the operation being tested. 

554 other : `TransformationWrapper` 

555 Other operand for the operation being tested. 

556 form : `NormalForm` 

557 Normal form being tested for. 

558 

559 Returns 

560 ------- 

561 satisfies : `bool` 

562 Whether ``operator.apply(self, other)`` satisfies the requirements 

563 of ``form``. 

564 

565 Notes 

566 ----- 

567 Caller guarantees that ``self`` and ``other`` are already normalized. 

568 """ 

569 return other._satisfiesDispatchAtomic(operator, self, form=form) 

570 

571 def _normalizeDispatch( 

572 self, operator: LogicalBinaryOperator, other: TransformationWrapper, *, form: NormalForm 

573 ) -> TransformationWrapper: 

574 """Return an expression equivalent to ``operator.apply(self, other)`` 

575 in a normal form. 

576 

577 The default implementation is appropriate for classes that never 

578 contain any AND or OR operations at all. 

579 

580 Parameters 

581 ---------- 

582 operator : `LogicalBinaryOperator` 

583 Operator for the operation being transformed. 

584 other : `TransformationWrapper` 

585 Other operand for the operation being transformed. 

586 form : `NormalForm` 

587 Normal form being transformed to. 

588 

589 Returns 

590 ------- 

591 normalized : `TransformationWrapper` 

592 An expression equivalent to ``operator.apply(self, other)`` 

593 for which ``normalized.satisfies(form)`` returns `True`. 

594 

595 Notes 

596 ----- 

597 Caller guarantees that ``self`` and ``other`` are already normalized. 

598 """ 

599 return other._normalizeDispatchAtomic(operator, self, form=form) 

600 

601 def _satisfiesDispatchAtomic( 

602 self, operator: LogicalBinaryOperator, other: TransformationWrapper, *, form: NormalForm 

603 ) -> bool: 

604 """Test whather ``operator.apply(other, self)`` is in a normal form. 

605 

606 The default implementation is appropriate for "atomic" classes that 

607 never contain any AND or OR operations at all. 

608 

609 Parameters 

610 ---------- 

611 operator : `LogicalBinaryOperator` 

612 Operator for the operation being tested. 

613 other : `TransformationWrapper` 

614 Other operand for the operation being tested. 

615 form : `NormalForm` 

616 Normal form being tested for. 

617 

618 Returns 

619 ------- 

620 satisfies : `bool` 

621 Whether ``operator.apply(other, self)`` satisfies the requirements 

622 of ``form``. 

623 

624 Notes 

625 ----- 

626 Should only be called by `_satisfiesDispatch` implementations; this 

627 guarantees that ``other`` is atomic and ``self`` is normalized. 

628 """ 

629 return True 

630 

631 def _normalizeDispatchAtomic( 

632 self, operator: LogicalBinaryOperator, other: TransformationWrapper, *, form: NormalForm 

633 ) -> TransformationWrapper: 

634 """Return an expression equivalent to ``operator.apply(other, self)``, 

635 in a normal form. 

636 

637 The default implementation is appropriate for "atomic" classes that 

638 never contain any AND or OR operations at all. 

639 

640 Parameters 

641 ---------- 

642 operator : `LogicalBinaryOperator` 

643 Operator for the operation being transformed. 

644 other : `TransformationWrapper` 

645 Other operand for the operation being transformed. 

646 form : `NormalForm` 

647 Normal form being transformed to. 

648 

649 Returns 

650 ------- 

651 normalized : `TransformationWrapper` 

652 An expression equivalent to ``operator.apply(other, self)`` 

653 for which ``normalized.satisfies(form)`` returns `True`. 

654 

655 Notes 

656 ----- 

657 Should only be called by `_normalizeDispatch` implementations; this 

658 guarantees that ``other`` is atomic and ``self`` is normalized. 

659 """ 

660 return operator.apply(other, self) 

661 

662 def _satisfiesDispatchBinary( 

663 self, 

664 outer: LogicalBinaryOperator, 

665 lhs: TransformationWrapper, 

666 inner: LogicalBinaryOperator, 

667 rhs: TransformationWrapper, 

668 *, 

669 form: NormalForm, 

670 ) -> bool: 

671 """Test whether ``outer.apply(self, inner.apply(lhs, rhs))`` is in a 

672 normal form. 

673 

674 The default implementation is appropriate for "atomic" classes that 

675 never contain any AND or OR operations at all. 

676 

677 Parameters 

678 ---------- 

679 outer : `LogicalBinaryOperator` 

680 Outer operator for the expression being tested. 

681 lhs : `TransformationWrapper` 

682 One inner operand for the expression being tested. 

683 inner : `LogicalBinaryOperator` 

684 Inner operator for the expression being tested. This may or may 

685 not be the same as ``outer``. 

686 rhs : `TransformationWrapper` 

687 The other inner operand for the expression being tested. 

688 form : `NormalForm` 

689 Normal form being transformed to. 

690 

691 Returns 

692 ------- 

693 satisfies : `bool` 

694 Whether ``outer.apply(self, inner.apply(lhs, rhs))`` satisfies the 

695 requirements of ``form``. 

696 

697 Notes 

698 ----- 

699 Should only be called by `_satisfiesDispatch` implementations; this 

700 guarantees that ``self``, ``lhs``, and ``rhs`` are all normalized. 

701 """ 

702 return form.allows(inner=inner, outer=outer) 

703 

704 def _normalizeDispatchBinary( 

705 self, 

706 outer: LogicalBinaryOperator, 

707 lhs: TransformationWrapper, 

708 inner: LogicalBinaryOperator, 

709 rhs: TransformationWrapper, 

710 *, 

711 form: NormalForm, 

712 ) -> TransformationWrapper: 

713 """Return an expression equivalent to 

714 ``outer.apply(self, inner.apply(lhs, rhs))``, meeting the guarantees of 

715 `normalize`. 

716 

717 The default implementation is appropriate for "atomic" classes that 

718 never contain any AND or OR operations at all. 

719 

720 Parameters 

721 ---------- 

722 outer : `LogicalBinaryOperator` 

723 Outer operator for the expression being transformed. 

724 lhs : `TransformationWrapper` 

725 One inner operand for the expression being transformed. 

726 inner : `LogicalBinaryOperator` 

727 Inner operator for the expression being transformed. 

728 rhs : `TransformationWrapper` 

729 The other inner operand for the expression being transformed. 

730 form : `NormalForm` 

731 Normal form being transformed to. 

732 

733 Returns 

734 ------- 

735 normalized : `TransformationWrapper` 

736 An expression equivalent to 

737 ``outer.apply(self, inner.apply(lhs, rhs))`` for which 

738 ``normalized.satisfies(form)`` returns `True`. 

739 

740 Notes 

741 ----- 

742 Should only be called by `_normalizeDispatch` implementations; this 

743 guarantees that ``self``, ``lhs``, and ``rhs`` are all normalized. 

744 """ 

745 if form.allows(inner=inner, outer=outer): 

746 return outer.apply(inner.apply(lhs, rhs), self) 

747 else: 

748 return inner.apply( 

749 outer.apply(lhs, self).normalize(form), 

750 outer.apply(rhs, self).normalize(form), 

751 ) 

752 

753 @abstractmethod 

754 def unwrap(self) -> Node: 

755 """Return a transformed expression tree. 

756 

757 Returns 

758 ------- 

759 tree : `Node` 

760 Tree node representing the same expression (and form) as ``self``. 

761 """ 

762 raise NotImplementedError() 

763 

764 

765class Opaque(TransformationWrapper): 

766 """A `TransformationWrapper` implementation for tree nodes that do not need 

767 to be modified in boolean expression transformations. 

768 

769 This includes all identifiers, literals, and operators whose arguments are 

770 not boolean. 

771 

772 Parameters 

773 ---------- 

774 node : `Node` 

775 Node wrapped by ``self``. 

776 precedence : `PrecedenceTier` 

777 Enumeration indicating how tightly this node is bound. 

778 """ 

779 

780 def __init__(self, node: Node, precedence: PrecedenceTier): 

781 self._node = node 

782 self._precedence = precedence 

783 

784 __slots__ = ("_node", "_precedence") 

785 

786 def __str__(self) -> str: 

787 return str(self._node) 

788 

789 @property 

790 def precedence(self) -> PrecedenceTier: 

791 # Docstring inherited from `TransformationWrapper`. 

792 return self._precedence 

793 

794 def not_(self) -> TransformationWrapper: 

795 # Docstring inherited from `TransformationWrapper`. 

796 return LogicalNot(self) 

797 

798 def unwrap(self) -> Node: 

799 # Docstring inherited from `TransformationWrapper`. 

800 return self._node 

801 

802 

803class LogicalNot(TransformationWrapper): 

804 """A `TransformationWrapper` implementation for logical NOT operations. 

805 

806 Parameters 

807 ---------- 

808 operand : `TransformationWrapper` 

809 Wrapper representing the operand of the NOT operation. 

810 

811 Notes 

812 ----- 

813 Instances should always be created by calling `not_` on an existing 

814 `TransformationWrapper` instead of calling `LogicalNot` directly. 

815 `LogicalNot` should only be called directly by `Opaque.not_`. This 

816 guarantees that double-negatives are simplified away and NOT operations 

817 are moved inside any OR and AND operations at construction. 

818 """ 

819 

820 def __init__(self, operand: Opaque): 

821 self._operand = operand 

822 

823 __slots__ = ("_operand",) 

824 

825 def __str__(self) -> str: 

826 return f"not({self._operand})" 

827 

828 @property 

829 def precedence(self) -> PrecedenceTier: 

830 # Docstring inherited from `TransformationWrapper`. 

831 return PrecedenceTier.UNARY 

832 

833 def not_(self) -> TransformationWrapper: 

834 # Docstring inherited from `TransformationWrapper`. 

835 return self._operand 

836 

837 def unwrap(self) -> Node: 

838 # Docstring inherited from `TransformationWrapper`. 

839 node = self._operand.unwrap() 

840 if PrecedenceTier.needsParens(self.precedence, self._operand.precedence): 

841 node = Parens(node) 

842 return UnaryOp("NOT", node) 

843 

844 

845class LogicalBinaryOperation(TransformationWrapper): 

846 """A `TransformationWrapper` implementation for logical OR and NOT 

847 implementations. 

848 

849 Parameters 

850 ---------- 

851 lhs : `TransformationWrapper` 

852 First operand. 

853 operator : `LogicalBinaryOperator` 

854 Enumeration representing the operator. 

855 rhs : `TransformationWrapper` 

856 Second operand. 

857 """ 

858 

859 def __init__( 

860 self, lhs: TransformationWrapper, operator: LogicalBinaryOperator, rhs: TransformationWrapper 

861 ): 

862 self._lhs = lhs 

863 self._operator = operator 

864 self._rhs = rhs 

865 self._satisfiesCache: dict[NormalForm, bool] = {} 

866 

867 __slots__ = ("_lhs", "_operator", "_rhs", "_satisfiesCache") 

868 

869 def __str__(self) -> str: 

870 return f"{self._operator.name.lower()}({self._lhs}, {self._rhs})" 

871 

872 @property 

873 def precedence(self) -> PrecedenceTier: 

874 # Docstring inherited from `TransformationWrapper`. 

875 return BINARY_OPERATOR_PRECEDENCE[self._operator.name] 

876 

877 def not_(self) -> TransformationWrapper: 

878 # Docstring inherited from `TransformationWrapper`. 

879 return LogicalBinaryOperation( 

880 self._lhs.not_(), 

881 LogicalBinaryOperator(not self._operator.value), 

882 self._rhs.not_(), 

883 ) 

884 

885 def satisfies(self, form: NormalForm) -> bool: 

886 # Docstring inherited from `TransformationWrapper`. 

887 r = self._satisfiesCache.get(form) 

888 if r is None: 

889 r = ( 

890 self._lhs.satisfies(form) 

891 and self._rhs.satisfies(form) 

892 and self._lhs._satisfiesDispatch(self._operator, self._rhs, form=form) 

893 ) 

894 self._satisfiesCache[form] = r 

895 return r 

896 

897 def normalize(self, form: NormalForm) -> TransformationWrapper: 

898 # Docstring inherited from `TransformationWrapper`. 

899 if self.satisfies(form): 

900 return self 

901 lhs = self._lhs.normalize(form) 

902 rhs = self._rhs.normalize(form) 

903 return lhs._normalizeDispatch(self._operator, rhs, form=form) 

904 

905 def flatten(self, operator: LogicalBinaryOperator) -> Iterator[TransformationWrapper]: 

906 # Docstring inherited from `TransformationWrapper`. 

907 if operator is self._operator: 

908 yield from self._lhs.flatten(operator) 

909 yield from self._rhs.flatten(operator) 

910 else: 

911 yield self 

912 

913 def _satisfiesDispatch( 

914 self, operator: LogicalBinaryOperator, other: TransformationWrapper, *, form: NormalForm 

915 ) -> bool: 

916 # Docstring inherited from `TransformationWrapper`. 

917 return other._satisfiesDispatchBinary(operator, self._lhs, self._operator, self._rhs, form=form) 

918 

919 def _normalizeDispatch( 

920 self, operator: LogicalBinaryOperator, other: TransformationWrapper, *, form: NormalForm 

921 ) -> TransformationWrapper: 

922 # Docstring inherited from `TransformationWrapper`. 

923 return other._normalizeDispatchBinary(operator, self._lhs, self._operator, self._rhs, form=form) 

924 

925 def _satisfiesDispatchAtomic( 

926 self, operator: LogicalBinaryOperator, other: TransformationWrapper, *, form: NormalForm 

927 ) -> bool: 

928 # Docstring inherited from `TransformationWrapper`. 

929 return form.allows(outer=operator, inner=self._operator) 

930 

931 def _normalizeDispatchAtomic( 

932 self, operator: LogicalBinaryOperator, other: TransformationWrapper, *, form: NormalForm 

933 ) -> TransformationWrapper: 

934 # Docstring inherited from `TransformationWrapper`. 

935 # Normalizes an expression of the form: 

936 # 

937 # operator.apply( 

938 # other, 

939 # self._operator.apply(self._lhs, self._rhs), 

940 # ) 

941 # 

942 if form.allows(outer=operator, inner=self._operator): 

943 return operator.apply(other, self) 

944 else: 

945 return self._operator.apply( 

946 operator.apply(other, self._lhs).normalize(form), 

947 operator.apply(other, self._rhs).normalize(form), 

948 ) 

949 

950 def _satisfiesDispatchBinary( 

951 self, 

952 outer: LogicalBinaryOperator, 

953 lhs: TransformationWrapper, 

954 inner: LogicalBinaryOperator, 

955 rhs: TransformationWrapper, 

956 *, 

957 form: NormalForm, 

958 ) -> bool: 

959 # Docstring inherited from `TransformationWrapper`. 

960 return form.allows(outer=outer, inner=inner) and form.allows(outer=outer, inner=self._operator) 

961 

962 def _normalizeDispatchBinary( 

963 self, 

964 outer: LogicalBinaryOperator, 

965 lhs: TransformationWrapper, 

966 inner: LogicalBinaryOperator, 

967 rhs: TransformationWrapper, 

968 *, 

969 form: NormalForm, 

970 ) -> TransformationWrapper: 

971 # Docstring inherited from `TransformationWrapper`. 

972 # Normalizes an expression of the form: 

973 # 

974 # outer.apply( 

975 # inner.apply(lhs, rhs), 

976 # self._operator.apply(self._lhs, self._rhs), 

977 # ) 

978 # 

979 if form.allows(inner=inner, outer=outer): 

980 other = inner.apply(lhs, rhs) 

981 if form.allows(inner=self._operator, outer=outer): 

982 return outer.apply(other, self) 

983 else: 

984 return self._operator.apply( 

985 outer.apply(other, self._lhs).normalize(form), 

986 outer.apply(other, self._rhs).normalize(form), 

987 ) 

988 else: 

989 if form.allows(inner=self._operator, outer=outer): 

990 return inner.apply( 

991 outer.apply(lhs, self).normalize(form), outer.apply(rhs, self).normalize(form) 

992 ) 

993 else: 

994 assert form.allows(inner=inner, outer=self._operator) 

995 return self._operator.apply( 

996 inner.apply( 

997 outer.apply(lhs, self._lhs).normalize(form), 

998 outer.apply(lhs, self._rhs).normalize(form), 

999 ), 

1000 inner.apply( 

1001 outer.apply(rhs, self._lhs).normalize(form), 

1002 outer.apply(rhs, self._rhs).normalize(form), 

1003 ), 

1004 ) 

1005 

1006 def unwrap(self) -> Node: 

1007 # Docstring inherited from `TransformationWrapper`. 

1008 lhsNode = self._lhs.unwrap() 

1009 if PrecedenceTier.needsParens(self.precedence, self._lhs.precedence): 

1010 lhsNode = Parens(lhsNode) 

1011 rhsNode = self._rhs.unwrap() 

1012 if PrecedenceTier.needsParens(self.precedence, self._rhs.precedence): 

1013 rhsNode = Parens(rhsNode) 

1014 return BinaryOp(lhsNode, self._operator.name, rhsNode) 

1015 

1016 

1017class TransformationVisitor(TreeVisitor[TransformationWrapper]): 

1018 """A `TreeVisitor` implementation that constructs a `TransformationWrapper` 

1019 tree when applied to a `Node` tree. 

1020 """ 

1021 

1022 def visitNumericLiteral(self, value: str, node: Node) -> TransformationWrapper: 

1023 # Docstring inherited from TreeVisitor.visitNumericLiteral 

1024 return Opaque(node, PrecedenceTier.TOKEN) 

1025 

1026 def visitStringLiteral(self, value: str, node: Node) -> TransformationWrapper: 

1027 # Docstring inherited from TreeVisitor.visitStringLiteral 

1028 return Opaque(node, PrecedenceTier.TOKEN) 

1029 

1030 def visitTimeLiteral(self, value: astropy.time.Time, node: Node) -> TransformationWrapper: