1# Copyright 2023 The Bazel Authors. All rights reserved. 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# http://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14 15"""Utilities for performing comparisons for Truth.""" 16 17load(":truth_common.bzl", "to_list") 18 19def _match_result_new(*, found_at, matched_value, matcher): 20 """Creates a "MatchResult" struct. 21 22 A `MatchResult` struct is information about how an expected value 23 matched to an actual value. 24 25 Args: 26 found_at: ([`int`]) the position in the actual container the match 27 occurred at. 28 matched_value: the actual value that caused the match 29 matcher: ([`Matcher`] | value) the value that matched 30 """ 31 return struct( 32 found_at = found_at, 33 matched_value = matched_value, 34 matcher = matcher, 35 ) 36 37# We use this name so it shows up nice in docs. 38# buildifier: disable=name-conventions 39MatchResult = struct( 40 new = _match_result_new, 41) 42 43def compare_contains_exactly_predicates(*, expect_contains, actual_container): 44 """Tells how and if values and predicates correspond 1:1 in the specified order. 45 46 * There must be a 1:1 correspondence between the container values and the 47 predicates. 48 * Multiplicity is respected (i.e., if the same predicate occurs twice, then 49 two distinct elements must match). 50 * Matching occurs in first-seen order. That is, a predicate will "consume" 51 the first value in `actual_container` it matches. 52 * The collection must match all the predicates, no more or less. 53 * Checking that the order of matches is the same as the passed-in matchers 54 order can be done by call `in_order()`. 55 56 Note that confusing results may occur if predicates with overlapping 57 match conditions are used. For example, given: 58 actual=["a", "ab", "abc"], 59 predicates=[<contains a>, <contains b>, <equals a>] 60 61 Then the result will be they aren't equal: the first two predicates 62 consume "a" and "ab", leaving only "abc" for the <equals a> predicate 63 to match against, which fails. 64 65 Args: 66 expect_contains: ([`collection`] of `Matcher`s) the predicates that must match. 67 To perform simple equalty, use `matching.equals_wrapper()`. 68 actual_container: ([`collection`]) The container to check within. 69 70 Returns: 71 struct with the following attributes: 72 * contains_exactly: ([`bool`]) True if all the predicates (and no others) 73 matched a distinct element; does not consider order. 74 * is_in_order: ([`bool`]) True if the actuals values matched in the same 75 order as the expected predicates. False if they were out of order. 76 If `contains_exactly=False`, this attribute is undefined. 77 * missing: [`list`] of [`Matcher`]s from `expect_contains` that did not find a 78 corresponding element in `actual_container`. 79 * unexpected: ([`list`]) values from `actual_container` that were not 80 present in `expect_contains`. 81 * matches: ([`list`] of [`MatchResult`]) information about which elements 82 in the two lists that matched each other. If 83 `contains_exactly=False`, this attribute is undefined. 84 """ 85 86 # The basic idea is treating the expected and actual lists as queues of 87 # remaining values to search for. This allows the multiplicity of values 88 # to be respected and ordering correctness to be computed. 89 # 90 # Each iteration, we "pop" an element off each queue and... 91 # * If the elements are equal, then all is good: ordering is still 92 # possible, and the required element is present. Start a new iteration. 93 # * Otherwise, we know ordering isn't possible anymore and need to 94 # answer two questions: 95 # 1. Is the actual value extra, or elsewhere in the expected values? 96 # 2. Is the expected value missing, or elsewhere in the actual values? 97 # If a value exists elsewhere in the other queue, then we have to 98 # remove it to prevent it from being searched for again in a later 99 # iteration. 100 # As we go along, we keep track of where expected values matched; this 101 # allows for better error reporting. 102 expect_contains = to_list(expect_contains) 103 actual_container = to_list(actual_container) 104 105 actual_queue = [] # List of (original pos, value) 106 for i, value in enumerate(actual_container): 107 actual_queue.append([i, value]) 108 109 expected_queue = [] # List of (original pos, value) 110 matches = [] # List of "MatchResult" structs 111 for i, value in enumerate(expect_contains): 112 expected_queue.append([i, value]) 113 matches.append(None) 114 115 missing = [] # List of expected values missing 116 unexpected = [] # List of actual values that weren't expected 117 ordered = True 118 119 # Start at -1 because the first iteration adds 1 120 pos = -1 121 loop = range(max(len(actual_queue), len(expected_queue))) 122 for _ in loop: 123 # Advancing the position is equivalent to removing the queues's head 124 pos += 1 125 if pos >= len(actual_queue) and pos >= len(expected_queue): 126 # Can occur when e.g. actual=[A, B], expected=[B] 127 break 128 if pos >= len(actual_queue): 129 # Fewer actual values than expected, so the rest are missing 130 missing.extend([v[1] for v in expected_queue[pos:]]) 131 break 132 if pos >= len(expected_queue): 133 # More actual values than expected, so the rest are unexpected 134 unexpected.extend([v[1] for v in actual_queue[pos:]]) 135 break 136 137 actual_entry = actual_queue[pos] 138 expected_entry = expected_queue[pos] 139 140 if expected_entry[1].match(actual_entry[1]): 141 # Happy path: both are equal and order is maintained. 142 matches[expected_entry[0]] = MatchResult.new( 143 found_at = actual_entry[0], 144 matched_value = actual_entry[1], 145 matcher = expected_entry[1], 146 ) 147 continue 148 ordered = False 149 found_at, found_entry = _list_find( 150 actual_queue, 151 lambda v: expected_entry[1].match(v[1]), 152 start = pos, 153 end = len(actual_queue), 154 ) 155 if found_at == -1: 156 missing.append(expected_entry[1]) 157 else: 158 # Remove it from the queue so a subsequent iteration doesn't 159 # try to search for it again. 160 actual_queue.pop(found_at) 161 matches[expected_entry[0]] = MatchResult.new( 162 found_at = found_entry[0], 163 matched_value = found_entry[1], 164 matcher = expected_entry[1], 165 ) 166 167 found_at, found_entry = _list_find( 168 expected_queue, 169 lambda entry: entry[1].match(actual_entry[1]), 170 start = pos, 171 end = len(expected_queue), 172 ) 173 if found_at == -1: 174 unexpected.append(actual_entry[1]) 175 else: 176 # Remove it from the queue so a subsequent iteration doesn't 177 # try to search for it again. 178 expected_queue.pop(found_at) 179 matches[found_entry[0]] = MatchResult.new( 180 found_at = actual_entry[0], 181 matched_value = actual_entry[1], 182 matcher = found_entry[1], 183 ) 184 185 return struct( 186 contains_exactly = not (missing or unexpected), 187 is_in_order = ordered, 188 missing = missing, 189 unexpected = unexpected, 190 matches = matches, 191 ) 192 193def _list_find(search_in, search_for, *, start = 0, end = None): 194 """Linear search a list for a value matching a predicate. 195 196 Args: 197 search_in: ([`list`]) the list to search within. 198 search_for: (callable) accepts 1 positional arg (the current value) 199 and returns `bool` (`True` if matched, `False` if not). 200 start: ([`int`]) the position within `search_in` to start at. Defaults 201 to `0` (start of list) 202 end: (optional [`int`]) the position within `search_in` to stop before 203 (i.e. the value is exclusive; given a list of length 5, specifying 204 `end=5` means it will search the whole list). Defaults to the length 205 of `search_in`. 206 Returns: 207 [`tuple`] of ([`int`] found_at, value). 208 * If the value was found, then `found_at` is the offset in `search_in` 209 it was found at, and matched value is the element at that offset. 210 * If the value was not found, then `found_at=-1`, and the matched 211 value is `None`. 212 """ 213 end = len(search_in) if end == None else end 214 pos = start 215 for _ in search_in: 216 if pos >= end: 217 return -1, None 218 value = search_in[pos] 219 if search_for(value): 220 return pos, value 221 pos += 1 222 return -1, None 223 224def compare_dicts(*, expected, actual): 225 """Compares two dicts, reporting differences. 226 227 Args: 228 expected: ([`dict`]) the desired state of `actual` 229 actual: ([`dict`]) the observed dict 230 Returns: 231 Struct with the following attributes: 232 * missing_keys: [`list`] of keys that were missing in `actual`, but present 233 in `expected` 234 * unexpected_keys: [`list`] of keys that were present in `actual`, but not 235 present in `expected` 236 * incorrect_entries: ([`dict`] of key -> [`DictEntryMismatch`]) of keys that 237 were in both dicts, but whose values were not equal. The value is 238 a "DictEntryMismatch" struct, which is defined as a struct with 239 attributes: 240 * `actual`: the value from `actual[key]` 241 * `expected`: the value from `expected[key]` 242 """ 243 all_keys = {key: None for key in actual.keys()} 244 all_keys.update({key: None for key in expected.keys()}) 245 missing_keys = [] 246 unexpected_keys = [] 247 incorrect_entries = {} 248 249 for key in sorted(all_keys): 250 if key not in actual: 251 missing_keys.append(key) 252 elif key not in expected: 253 unexpected_keys.append(key) 254 else: 255 actual_value = actual[key] 256 expected_value = expected[key] 257 if actual_value != expected_value: 258 incorrect_entries[key] = struct( 259 actual = actual_value, 260 expected = expected_value, 261 ) 262 263 return struct( 264 missing_keys = missing_keys, 265 unexpected_keys = unexpected_keys, 266 incorrect_entries = incorrect_entries, 267 ) 268