Coverage for tests/test_normalFormExpression.py: 36%

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 

28 

29import random 

30import unittest 

31from typing import Any 

32from uuid import UUID 

33 

34import astropy.time 

35 

36from lsst.daf.butler.registry.queries.expressions.normalForm import ( 

37 NormalForm, 

38 NormalFormExpression, 

39 TransformationVisitor, 

40) 

41from lsst.daf.butler.registry.queries.expressions.parser import Node, ParserYacc, TreeVisitor 

42 

43 

44class BooleanEvaluationTreeVisitor(TreeVisitor[bool]): 

45 """A `TreeVisitor` implementation that evaluates boolean expressions given 

46 boolean values for identifiers. 

47 """ 

48 

49 def __init__(self, binds: dict[str, Any] = {}, **kwargs: bool): 

50 self.binds = binds 

51 self.values = kwargs 

52 

53 def init(self, form: NormalForm) -> None: 

54 self.form = form 

55 

56 def visitNumericLiteral(self, value: str, node: Node) -> bool: 

57 # Docstring inherited from TreeVisitor.visitNumericLiteral 

58 raise NotImplementedError() 

59 

60 def visitStringLiteral(self, value: str, node: Node) -> bool: 

61 # Docstring inherited from TreeVisitor.visitStringLiteral 

62 raise NotImplementedError() 

63 

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

65 # Docstring inherited from TreeVisitor.visitTimeLiteral 

66 raise NotImplementedError() 

67 

68 def visitUuidLiteral(self, value: UUID, node: Node) -> bool: 

69 # Docstring inherited from TreeVisitor.visitUuidLiteral 

70 raise NotImplementedError() 

71 

72 def visitIdentifier(self, name: str, node: Node) -> bool: 

73 # Docstring inherited from TreeVisitor.visitIdentifier 

74 return self.values[name] 

75 

76 def visitBind(self, name: str, node: Node) -> bool: 

77 # Docstring inherited from TreeVisitor.visitIdentifier 

78 return self.binds[name] 

79 

80 def visitUnaryOp( 

81 self, 

82 operator: str, 

83 operand: bool, 

84 node: Node, 

85 ) -> bool: 

86 # Docstring inherited from TreeVisitor.visitUnaryOp 

87 if operator == "NOT": 

88 return not operand 

89 raise NotImplementedError() 

90 

91 def visitBinaryOp( 

92 self, 

93 operator: str, 

94 lhs: bool, 

95 rhs: bool, 

96 node: Node, 

97 ) -> bool: 

98 # Docstring inherited from TreeVisitor.visitBinaryOp 

99 if operator == "AND": 

100 return lhs and rhs 

101 if operator == "OR": 

102 return lhs or rhs 

103 raise NotImplementedError() 

104 

105 def visitIsIn( 

106 self, 

107 lhs: bool, 

108 values: list[bool], 

109 not_in: bool, 

110 node: Node, 

111 ) -> bool: 

112 # Docstring inherited from TreeVisitor.visitIsIn 

113 raise NotImplementedError() 

114 

115 def visitParens(self, expression: bool, node: Node) -> bool: 

116 # Docstring inherited from TreeVisitor.visitParens 

117 return expression 

118 

119 def visitRangeLiteral(self, start: int, stop: int, stride: int | None, node: Node) -> bool: 

120 # Docstring inherited from TreeVisitor.visitRangeLiteral 

121 raise NotImplementedError() 

122 

123 def visitPointNode(self, ra: float, dec: float, node: Node) -> bool: 

124 raise NotImplementedError("Not implemented for bool operations") 

125 

126 def visitCircleNode(self, ra: float, dec: float, radius: float, node: Node) -> bool: 

127 raise NotImplementedError("Not implemented for bool operations") 

128 

129 def visitBoxNode(self, ra: float, dec: float, width: float, height: float, node: Node) -> bool: 

130 raise NotImplementedError("Not implemented for bool operations") 

131 

132 def visitPolygonNode(self, vertices: list[tuple[float, float]], node: Node) -> bool: 

133 raise NotImplementedError("Not implemented for bool operations") 

134 

135 def visitRegionNode(self, pos: str, node: Node) -> bool: 

136 raise NotImplementedError("Not implemented for bool operations") 

137 

138 def visitTupleNode(self, items: tuple, node: Node) -> bool: 

139 raise NotImplementedError("Not implemented for bool operations") 

140 

141 def visitGlobNode(self, expression: str, pattern: str, node: Node) -> bool: 

142 raise NotImplementedError("Not implemented for bool operations") 

143 

144 

145class NormalFormExpressionTestCase(unittest.TestCase): 

146 """Tests for `NormalFormExpression` and its helper classes.""" 

147 

148 def check( 

149 self, 

150 expression: str, 

151 conjunctive: str | bool = False, 

152 disjunctive: str | bool = False, 

153 ) -> None: 

154 """Compare the results of transforming an expression to normal form 

155 against given expected values. 

156 

157 Parameters 

158 ---------- 

159 expression : `str` 

160 Expression to parse and transform. 

161 conjunctive : `str` or `bool` 

162 The expected string form of the expression after transformation 

163 to conjunctive normal form, or `True` to indicate that 

164 ``expression`` should already be in that form. `False` to skip 

165 tests on this form. 

166 disjunctive : `str` or `bool` 

167 Same as ``conjunctive``, but for disjunctive normal form. 

168 """ 

169 with self.subTest(expression): 

170 parser = ParserYacc() 

171 originalTree = parser.parse(expression) 

172 wrapper = originalTree.visit(TransformationVisitor()) 

173 trees = {form: NormalFormExpression.fromTree(originalTree, form).toTree() for form in NormalForm} 

174 if conjunctive is True: # expected to be conjunctive already 

175 self.assertTrue(wrapper.satisfies(NormalForm.CONJUNCTIVE), msg=str(wrapper)) 

176 elif conjunctive: # str to expect after normalization to conjunctive 

177 self.assertEqual(str(trees[NormalForm.CONJUNCTIVE]), conjunctive) 

178 if disjunctive is True: # expected to be disjunctive already 

179 self.assertTrue(wrapper.satisfies(NormalForm.DISJUNCTIVE), msg=str(wrapper)) 

180 elif disjunctive: # str to expect after normalization to disjunctive 

181 self.assertEqual(str(trees[NormalForm.DISJUNCTIVE]), disjunctive) 

182 for _ in range(10): 

183 values = {k: bool(random.randint(0, 1)) for k in "ABCDEF"} 

184 visitor = BooleanEvaluationTreeVisitor(**values) 

185 expected = originalTree.visit(visitor) 

186 for name, tree in trees.items(): 

187 self.assertEqual(expected, tree.visit(visitor), msg=name) 

188 

189 def testNormalize(self): 

190 self.check("A AND B", conjunctive=True, disjunctive=True) 

191 self.check("A OR B", conjunctive=True, disjunctive=True) 

192 self.check("NOT (A OR B)", conjunctive="NOT A AND NOT B", disjunctive="NOT A AND NOT B") 

193 self.check("NOT (A AND B)", conjunctive="NOT A OR NOT B", disjunctive="NOT A OR NOT B") 

194 self.check( 

195 "NOT (A AND (NOT B OR C))", 

196 conjunctive="(NOT A OR B) AND (NOT A OR NOT C)", 

197 disjunctive=True, 

198 ) 

199 self.check( 

200 "NOT (A OR (B AND NOT C))", 

201 conjunctive=True, 

202 disjunctive="(NOT A AND NOT B) OR (NOT A AND C)", 

203 ) 

204 self.check( 

205 "A AND (B OR C OR D)", 

206 conjunctive=True, 

207 disjunctive="(A AND B) OR (A AND C) OR (A AND D)", 

208 ) 

209 self.check( 

210 "A OR (B AND C AND D)", 

211 disjunctive=True, 

212 conjunctive="(A OR B) AND (A OR C) AND (A OR D)", 

213 ) 

214 self.check( 

215 "A AND (B OR NOT C) AND (NOT D OR E OR F)", 

216 conjunctive=True, 

217 disjunctive=( 

218 "(A AND B AND NOT D) OR (A AND B AND E) OR (A AND B AND F) " 

219 "OR (A AND NOT C AND NOT D) OR (A AND NOT C AND E) OR (A AND NOT C AND F)" 

220 ), 

221 ) 

222 self.check( 

223 "A OR (B AND NOT C) OR (NOT D AND E AND F)", 

224 conjunctive=( 

225 "(A OR B OR NOT D) AND (A OR B OR E) AND (A OR B OR F) " 

226 "AND (A OR NOT C OR NOT D) AND (A OR NOT C OR E) AND (A OR NOT C OR F)" 

227 ), 

228 disjunctive=True, 

229 ) 

230 self.check( 

231 "(A OR (B AND NOT (C OR (NOT D AND E)))) OR F", 

232 conjunctive="(A OR B OR F) AND (A OR NOT C OR F) AND (A OR D OR NOT E OR F)", 

233 disjunctive="A OR (B AND NOT C AND D) OR (B AND NOT C AND NOT E) OR F", 

234 ) 

235 

236 

237if __name__ == "__main__": 

238 unittest.main()