microsoft/qdk
Publicmirrored fromhttps://github.com/microsoft/qdkAvailable
compiler/qsc_data_structures/src/namespaces/tests.rs
447lines · modecode
| 1 | // Copyright (c) Microsoft Corporation. |
| 2 | // Licensed under the MIT License. |
| 3 | |
| 4 | // allowing needless raw hashes here because we auto-update these expected outputs |
| 5 | // and don't want to risk weird breakages |
| 6 | |
| 7 | #![allow(clippy::needless_raw_string_hashes)] |
| 8 | |
| 9 | use expect_test::expect; |
| 10 | |
| 11 | use super::*; |
| 12 | |
| 13 | #[allow(clippy::too_many_lines)] |
| 14 | #[test] |
| 15 | fn test_tree_construction() { |
| 16 | let mut root = NamespaceTreeRoot::default(); |
| 17 | for i in 0..3 { |
| 18 | for j in 'a'..'d' { |
| 19 | let _ = root.insert_or_find_namespace( |
| 20 | vec![Rc::from(format!("ns{i}")), Rc::from(format!("ns{j}"))].into_iter(), |
| 21 | ); |
| 22 | } |
| 23 | } |
| 24 | expect![[r#" |
| 25 | NamespaceTreeRoot |
| 26 | |
| 27 | children: [ |
| 28 | ns1(id 5) { |
| 29 | children: [ |
| 30 | nsc(id 8) {empty node}, |
| 31 | nsb(id 7) {empty node}, |
| 32 | nsa(id 6) {empty node}, |
| 33 | ] |
| 34 | }, |
| 35 | ns0(id 1) { |
| 36 | children: [ |
| 37 | nsc(id 4) {empty node}, |
| 38 | nsb(id 3) {empty node}, |
| 39 | nsa(id 2) {empty node}, |
| 40 | ] |
| 41 | }, |
| 42 | ns2(id 9) { |
| 43 | children: [ |
| 44 | nsc(id 12) {empty node}, |
| 45 | nsb(id 11) {empty node}, |
| 46 | nsa(id 10) {empty node}, |
| 47 | ] |
| 48 | }, |
| 49 | ] |
| 50 | } |
| 51 | "#]] |
| 52 | .assert_debug_eq(&root); |
| 53 | } |
| 54 | |
| 55 | #[allow(clippy::too_many_lines)] |
| 56 | #[test] |
| 57 | fn test_find_id() { |
| 58 | let mut root = NamespaceTreeRoot::default(); |
| 59 | let mut id_buf = vec![]; |
| 60 | for i in 0..3 { |
| 61 | for j in 'a'..'d' { |
| 62 | id_buf.push(root.insert_or_find_namespace( |
| 63 | vec![Rc::from(format!("ns{i}")), Rc::from(format!("ns{j}"))].into_iter(), |
| 64 | )); |
| 65 | } |
| 66 | id_buf.push(root.insert_or_find_namespace(vec![Rc::from(format!("ns{i}"))].into_iter())); |
| 67 | } |
| 68 | let mut result_buf = vec![]; |
| 69 | for id in id_buf { |
| 70 | result_buf.push(root.find_namespace_by_id(&id)); |
| 71 | } |
| 72 | expect![[r#" |
| 73 | [ |
| 74 | ( |
| 75 | [ |
| 76 | "ns0", |
| 77 | "nsa", |
| 78 | ], |
| 79 | RefCell { |
| 80 | value: empty node}, |
| 81 | }, |
| 82 | ), |
| 83 | ( |
| 84 | [ |
| 85 | "ns0", |
| 86 | "nsb", |
| 87 | ], |
| 88 | RefCell { |
| 89 | value: empty node}, |
| 90 | }, |
| 91 | ), |
| 92 | ( |
| 93 | [ |
| 94 | "ns0", |
| 95 | "nsc", |
| 96 | ], |
| 97 | RefCell { |
| 98 | value: empty node}, |
| 99 | }, |
| 100 | ), |
| 101 | ( |
| 102 | [ |
| 103 | "ns0", |
| 104 | ], |
| 105 | RefCell { |
| 106 | value: |
| 107 | children: [ |
| 108 | nsc(id 4) {empty node}, |
| 109 | nsb(id 3) {empty node}, |
| 110 | nsa(id 2) {empty node}, |
| 111 | ] |
| 112 | }, |
| 113 | }, |
| 114 | ), |
| 115 | ( |
| 116 | [ |
| 117 | "ns1", |
| 118 | "nsa", |
| 119 | ], |
| 120 | RefCell { |
| 121 | value: empty node}, |
| 122 | }, |
| 123 | ), |
| 124 | ( |
| 125 | [ |
| 126 | "ns1", |
| 127 | "nsb", |
| 128 | ], |
| 129 | RefCell { |
| 130 | value: empty node}, |
| 131 | }, |
| 132 | ), |
| 133 | ( |
| 134 | [ |
| 135 | "ns1", |
| 136 | "nsc", |
| 137 | ], |
| 138 | RefCell { |
| 139 | value: empty node}, |
| 140 | }, |
| 141 | ), |
| 142 | ( |
| 143 | [ |
| 144 | "ns1", |
| 145 | ], |
| 146 | RefCell { |
| 147 | value: |
| 148 | children: [ |
| 149 | nsc(id 8) {empty node}, |
| 150 | nsb(id 7) {empty node}, |
| 151 | nsa(id 6) {empty node}, |
| 152 | ] |
| 153 | }, |
| 154 | }, |
| 155 | ), |
| 156 | ( |
| 157 | [ |
| 158 | "ns2", |
| 159 | "nsa", |
| 160 | ], |
| 161 | RefCell { |
| 162 | value: empty node}, |
| 163 | }, |
| 164 | ), |
| 165 | ( |
| 166 | [ |
| 167 | "ns2", |
| 168 | "nsb", |
| 169 | ], |
| 170 | RefCell { |
| 171 | value: empty node}, |
| 172 | }, |
| 173 | ), |
| 174 | ( |
| 175 | [ |
| 176 | "ns2", |
| 177 | "nsc", |
| 178 | ], |
| 179 | RefCell { |
| 180 | value: empty node}, |
| 181 | }, |
| 182 | ), |
| 183 | ( |
| 184 | [ |
| 185 | "ns2", |
| 186 | ], |
| 187 | RefCell { |
| 188 | value: |
| 189 | children: [ |
| 190 | nsc(id 12) {empty node}, |
| 191 | nsb(id 11) {empty node}, |
| 192 | nsa(id 10) {empty node}, |
| 193 | ] |
| 194 | }, |
| 195 | }, |
| 196 | ), |
| 197 | ] |
| 198 | "#]] |
| 199 | .assert_debug_eq(&result_buf); |
| 200 | } |
| 201 | // test that after inserting lots of namespaces, all ids are unique and sequential |
| 202 | #[test] |
| 203 | fn test_insert_or_find_namespace() { |
| 204 | let mut root = NamespaceTreeRoot::default(); |
| 205 | let mut ids: Vec<usize> = vec![]; |
| 206 | for i in 0..3 { |
| 207 | for j in 'a'..'d' { |
| 208 | let id = root.insert_or_find_namespace( |
| 209 | vec![Rc::from(format!("ns{i}")), Rc::from(format!("ns{j}"))].into_iter(), |
| 210 | ); |
| 211 | ids.push(id.into()); |
| 212 | } |
| 213 | } |
| 214 | let mut ids_sorted = ids.clone(); |
| 215 | ids_sorted.sort_unstable(); |
| 216 | ids_sorted.dedup(); |
| 217 | // there should be no duplicate or out-of-order ids |
| 218 | assert_eq!(ids_sorted, ids); |
| 219 | expect![[r#" |
| 220 | [ |
| 221 | 2, |
| 222 | 3, |
| 223 | 4, |
| 224 | 6, |
| 225 | 7, |
| 226 | 8, |
| 227 | 10, |
| 228 | 11, |
| 229 | 12, |
| 230 | ] |
| 231 | "#]] |
| 232 | .assert_debug_eq(&ids); |
| 233 | } |
| 234 | |
| 235 | // test for get_namespace_id |
| 236 | #[test] |
| 237 | fn test_get_namespace_id() { |
| 238 | let mut root = NamespaceTreeRoot::default(); |
| 239 | let mut names_to_query_buf = vec![]; |
| 240 | for i in 0..3 { |
| 241 | for j in 'a'..'d' { |
| 242 | let name = vec![Rc::from(format!("ns{i}")), Rc::from(format!("ns{j}"))]; |
| 243 | let _ = root.insert_or_find_namespace(name.clone()); |
| 244 | names_to_query_buf.push(name); |
| 245 | } |
| 246 | let name = vec![Rc::from(format!("ns{i}"))]; |
| 247 | let _ = root.insert_or_find_namespace(name.clone()); |
| 248 | names_to_query_buf.push(name); |
| 249 | } |
| 250 | let mut result_buf = vec![]; |
| 251 | for name in names_to_query_buf { |
| 252 | result_buf.push(root.get_namespace_id(name.iter().map(|x| &**x))); |
| 253 | } |
| 254 | expect![[r#" |
| 255 | [ |
| 256 | Some( |
| 257 | NamespaceId( |
| 258 | 2, |
| 259 | ), |
| 260 | ), |
| 261 | Some( |
| 262 | NamespaceId( |
| 263 | 3, |
| 264 | ), |
| 265 | ), |
| 266 | Some( |
| 267 | NamespaceId( |
| 268 | 4, |
| 269 | ), |
| 270 | ), |
| 271 | Some( |
| 272 | NamespaceId( |
| 273 | 1, |
| 274 | ), |
| 275 | ), |
| 276 | Some( |
| 277 | NamespaceId( |
| 278 | 6, |
| 279 | ), |
| 280 | ), |
| 281 | Some( |
| 282 | NamespaceId( |
| 283 | 7, |
| 284 | ), |
| 285 | ), |
| 286 | Some( |
| 287 | NamespaceId( |
| 288 | 8, |
| 289 | ), |
| 290 | ), |
| 291 | Some( |
| 292 | NamespaceId( |
| 293 | 5, |
| 294 | ), |
| 295 | ), |
| 296 | Some( |
| 297 | NamespaceId( |
| 298 | 10, |
| 299 | ), |
| 300 | ), |
| 301 | Some( |
| 302 | NamespaceId( |
| 303 | 11, |
| 304 | ), |
| 305 | ), |
| 306 | Some( |
| 307 | NamespaceId( |
| 308 | 12, |
| 309 | ), |
| 310 | ), |
| 311 | Some( |
| 312 | NamespaceId( |
| 313 | 9, |
| 314 | ), |
| 315 | ), |
| 316 | ] |
| 317 | "#]] |
| 318 | .assert_debug_eq(&result_buf); |
| 319 | } |
| 320 | |
| 321 | #[allow(clippy::too_many_lines)] |
| 322 | #[test] |
| 323 | fn test_tree_iter() { |
| 324 | let mut root = NamespaceTreeRoot::default(); |
| 325 | for i in 0..3 { |
| 326 | for j in 'a'..'d' { |
| 327 | let _ = root.insert_or_find_namespace( |
| 328 | vec![Rc::from(format!("ns{i}")), Rc::from(format!("ns{j}"))].into_iter(), |
| 329 | ); |
| 330 | } |
| 331 | } |
| 332 | |
| 333 | let result = root.iter().collect::<Vec<_>>(); |
| 334 | expect![[r#" |
| 335 | [ |
| 336 | [ |
| 337 | [], |
| 338 | ], |
| 339 | [ |
| 340 | [ |
| 341 | "ns0", |
| 342 | ], |
| 343 | ], |
| 344 | [ |
| 345 | [ |
| 346 | "ns0", |
| 347 | "nsa", |
| 348 | ], |
| 349 | [ |
| 350 | "ns0", |
| 351 | "nsa", |
| 352 | ], |
| 353 | ], |
| 354 | [ |
| 355 | [ |
| 356 | "ns0", |
| 357 | "nsb", |
| 358 | ], |
| 359 | [ |
| 360 | "ns0", |
| 361 | "nsb", |
| 362 | ], |
| 363 | ], |
| 364 | [ |
| 365 | [ |
| 366 | "ns0", |
| 367 | "nsc", |
| 368 | ], |
| 369 | [ |
| 370 | "ns0", |
| 371 | "nsc", |
| 372 | ], |
| 373 | ], |
| 374 | [ |
| 375 | [ |
| 376 | "ns1", |
| 377 | ], |
| 378 | ], |
| 379 | [ |
| 380 | [ |
| 381 | "ns1", |
| 382 | "nsa", |
| 383 | ], |
| 384 | [ |
| 385 | "ns1", |
| 386 | "nsa", |
| 387 | ], |
| 388 | ], |
| 389 | [ |
| 390 | [ |
| 391 | "ns1", |
| 392 | "nsb", |
| 393 | ], |
| 394 | [ |
| 395 | "ns1", |
| 396 | "nsb", |
| 397 | ], |
| 398 | ], |
| 399 | [ |
| 400 | [ |
| 401 | "ns1", |
| 402 | "nsc", |
| 403 | ], |
| 404 | [ |
| 405 | "ns1", |
| 406 | "nsc", |
| 407 | ], |
| 408 | ], |
| 409 | [ |
| 410 | [ |
| 411 | "ns2", |
| 412 | ], |
| 413 | ], |
| 414 | [ |
| 415 | [ |
| 416 | "ns2", |
| 417 | "nsa", |
| 418 | ], |
| 419 | [ |
| 420 | "ns2", |
| 421 | "nsa", |
| 422 | ], |
| 423 | ], |
| 424 | [ |
| 425 | [ |
| 426 | "ns2", |
| 427 | "nsb", |
| 428 | ], |
| 429 | [ |
| 430 | "ns2", |
| 431 | "nsb", |
| 432 | ], |
| 433 | ], |
| 434 | [ |
| 435 | [ |
| 436 | "ns2", |
| 437 | "nsc", |
| 438 | ], |
| 439 | [ |
| 440 | "ns2", |
| 441 | "nsc", |
| 442 | ], |
| 443 | ], |
| 444 | ] |
| 445 | "#]] |
| 446 | .assert_debug_eq(&result); |
| 447 | } |
| 448 | |