Recursively traceback from the query, i.e. the conclusion.
(
query: problem.Dependency,
)
| 144 | |
| 145 | |
| 146 | def recursive_traceback( |
| 147 | query: problem.Dependency, |
| 148 | ) -> list[tuple[list[problem.Dependency], list[problem.Dependency]]]: |
| 149 | """Recursively traceback from the query, i.e. the conclusion.""" |
| 150 | visited = set() |
| 151 | log = [] |
| 152 | stack = [] |
| 153 | |
| 154 | def read(q: problem.Dependency) -> None: |
| 155 | q = q.remove_loop() |
| 156 | hashed = q.hashed() |
| 157 | if hashed in visited: |
| 158 | return |
| 159 | |
| 160 | if hashed[0] in ['ncoll', 'npara', 'nperp', 'diff', 'sameside']: |
| 161 | return |
| 162 | |
| 163 | nonlocal stack |
| 164 | |
| 165 | stack.append(hashed) |
| 166 | prems = [] |
| 167 | |
| 168 | if q.rule_name != problem.CONSTRUCTION_RULE: |
| 169 | all_deps = [] |
| 170 | dep_names = set() |
| 171 | for d in q.why: |
| 172 | if d.hashed() in dep_names: |
| 173 | continue |
| 174 | dep_names.add(d.hashed()) |
| 175 | all_deps.append(d) |
| 176 | |
| 177 | for d in all_deps: |
| 178 | h = d.hashed() |
| 179 | if h not in visited: |
| 180 | read(d) |
| 181 | if h in visited: |
| 182 | prems.append(d) |
| 183 | |
| 184 | visited.add(hashed) |
| 185 | hashs = sorted([d.hashed() for d in prems]) |
| 186 | found = False |
| 187 | for ps, qs in log: |
| 188 | if sorted([d.hashed() for d in ps]) == hashs: |
| 189 | qs += [q] |
| 190 | found = True |
| 191 | break |
| 192 | if not found: |
| 193 | log.append((prems, [q])) |
| 194 | |
| 195 | stack.pop(-1) |
| 196 | |
| 197 | read(query) |
| 198 | |
| 199 | # post process log: separate multi-conclusion lines |
| 200 | log_, log = log, [] |
| 201 | for ps, qs in log_: |
| 202 | for q in qs: |
| 203 | log.append((ps, [q])) |