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