src/vpid.rs

   1 // Copyright 2020-2021 Ian Jackson and contributors to Otter
   2 // SPDX-License-Identifier: AGPL-3.0-or-later
   3 // There is NO WARRANTY.
   4
   5 use super::*;
   6
   7 #[derive(Clone,Debug,Default,Serialize,Deserialize)]
   8 pub struct PerPlayerIdMap {
   9   pub(in super) f: SecondarySlotMap<PieceId, VisiblePieceId>,
  10   pub(in super) r: DenseSlotMap<VisiblePieceId, PieceId>,
  11 }
  12
  13 impl PerPlayerIdMap {
  14   pub fn fwd(&self, piece: PieceId) -> Option<VisiblePieceId> {
  15     Some(*self.f.get(piece)?)
  16   }
  17   pub fn rev(&self, vis: VisiblePieceId) -> Option<PieceId> {
  18     Some(*self.r.get(vis)?)
  19   }
  20
  21   fn fwd_or_insert_internal<R, VF, OF>
  22     (&mut self, piece: PieceId, vf: VF, of: OF) -> R
  23   where VF: FnOnce(VisiblePieceId) -> R,
  24         OF: FnOnce(secondary::OccupiedEntry<PieceId,VisiblePieceId>) -> R,
  25   {
  26     match self.f.entry(piece).expect("stale PieceId !") {
  27       secondary::Entry::Vacant(mut vac) => {
  28         if let Some((_, stale_vis)) = vac.remove_stale_entry() {
  29           self.r.remove(stale_vis);
  30         }
  31         let vis = self.r.insert(piece);
  32         vac.insert(vis);
  33         vf(vis)
  34       }
  35       secondary::Entry::Occupied(occ) => {
  36         of(occ)
  37       }
  38     }
  39   }
  40
  41   pub fn insert(&mut self, piece: PieceId) {
  42     self.fwd_or_insert_internal(piece, |_vis|(), |vis|{
  43       panic!("duplicate insert of {:?} {:?}", piece, vis)
  44     })
  45   }
  46
  47   pub fn fwd_or_insert(&mut self, piece: PieceId) -> VisiblePieceId {
  48     self.fwd_or_insert_internal(piece, |vis|vis, |occ| *occ.get())
  49   }
  50 }
  51
  52 pub type NotchNumber = u32;
  53
  54 define_index_type!{
  55   pub struct Notch = NotchNumber;
  56 }
  57
  58 impl From<Notch> for u32 {
  59   fn from(n: Notch) -> u32 { n.index().try_into().unwrap() }
  60 }
  61
  62 type NotchPtr = Option<Notch>;
  63
  64 #[derive(Clone,Copy,Debug,Serialize,Deserialize)]
  65 #[derive(Eq,PartialEq)]
  66 enum NotchRecord {
  67   Free(NotchPtr),
  68   Piece(PieceId),
  69 }
  70 type NR = NotchRecord;
  71
  72 impl NotchRecord {
  73   fn piece(&self) -> Option<PieceId> { match self {
  74     &NR::Piece(p) => Some(p),
  75     &NR::Free(_) => None,
  76   }}
  77
  78   fn unwrap_free(&self) -> NotchPtr { match self {
  79     &NR::Free(ptr) => ptr,
  80     _ => panic!(),
  81   }}
  82
  83   fn unwrap_free_mut(&mut self) -> &mut NotchPtr { match self {
  84     NR::Free(ptr) => ptr,
  85     _ => panic!(),
  86   }}
  87 }
  88
  89 #[derive(Clone,Debug,Serialize,Deserialize,Default)]
  90 pub struct Notches {
  91   freelist: NotchPtr,
  92   table: IndexVec<Notch, NotchRecord>,
  93   zg: IndexVec<Notch, Generation>, // last time notch was (re)filled
  94   used: NotchNumber,
  95 }
  96
  97 impl Occultation {
  98   pub fn notch_zg(&self, notch: Notch) -> Option<Generation> {
  99     self.notches.zg.get(notch).copied()
 100   }
 101 }
 102
 103 impl Notches {
 104   pub fn iter<'i>(&'i self) -> impl Iterator<Item=PieceId> + 'i {
 105     self.table.iter()
 106       .filter_map(|nr| match nr {
 107         NR::Free(_) => None,
 108         &NR::Piece(p) => Some(p),
 109       })
 110   }
 111
 112   /// correctness: piece must not already be in this `Notches`
 113   pub fn insert(&mut self, zg: Generation, piece: PieceId) -> Notch {
 114     let new = NR::Piece(piece);
 115     let notch = match self.freelist.take() {
 116       None => {
 117         let a = self.table.push(new);
 118         let b = self.zg.push(zg);
 119         // gs.max_z was updated when we created the occultation
 120         assert_eq!(a,b);
 121         a
 122       },
 123       Some(old_free_head) => {
 124         self.freelist = self.table[old_free_head].unwrap_free();
 125         self.table[old_free_head] = new;
 126         self.zg[old_free_head] = zg;
 127         old_free_head
 128       },
 129     };
 130     self.used += 1;
 131     notch
 132   }
 133
 134   #[throws(IE)]
 135   pub fn remove(&mut self, piece: PieceId, notch: Notch) {
 136     match self.table.get(notch) {
 137       Some(&NR::Piece(p)) if p == piece => { },
 138       _ => throw!(internal_error_bydebug(&(piece, notch, self))),
 139     }
 140     {
 141       let mut insert_here = &mut self.freelist;
 142       loop {
 143         let next = *insert_here;
 144         let next = if let Some(y) = next { y } else { break };
 145         if notch < next { break }
 146         if notch == next { panic!() };
 147         let next = &mut self.table[next];
 148         insert_here = next.unwrap_free_mut();
 149       }
 150       // Now either *insert_here==NULL or notch < insert_here->next
 151       let old_next = mem::replace(insert_here, Some(notch));
 152       self.table[notch] = NR::Free(old_next);
 153       self.used -= 1;
 154     }
 155   }
 156
 157   pub fn len(&self) -> NotchNumber { self.used }
 158   pub fn is_empty(&self) -> bool { self.used == 0 }
 159
 160   #[cfg(not(miri))]
 161   #[cfg(test)]
 162   fn check(&self) {
 163     let mut count_free = 0;
 164     let mut walk = self.freelist;
 165     while let Some(here) = walk {
 166       count_free += 1;
 167       let next_walk = self.table[here].unwrap_free();
 168       if let Some(more) = next_walk {
 169         assert!(more > here);
 170       }
 171       walk = next_walk;
 172     }
 173     assert_eq!(
 174       count_free,
 175       self.table.iter()
 176         .filter(|nr| matches!(nr, NR::Free(_)))
 177         .count()
 178     );
 179     let pieces = self.table.iter()
 180       .filter_map(|nr| if let NR::Piece(p) = nr { Some(p) } else { None })
 181       .collect::<HashSet<_>>();
 182     assert_eq!(
 183       self.used as usize,
 184       pieces.len(),
 185     );
 186     assert_eq!(
 187       count_free + pieces.len(),
 188       self.table.len(),
 189     );
 190   }
 191 }
 192
 193 #[cfg(not(miri))]
 194 #[test]
 195 fn exhaustive() {
 196   enum Can {
 197     Insert(PieceId),
 198     Remove(PieceId),
 199   }
 200   impl Debug for Can {
 201     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(),fmt::Error> {
 202       let (c, p) = match self {
 203         Can::Insert(p) => ('+', p),
 204         Can::Remove(p) => ('-', p),
 205       };
 206       let (idx, _vsn) = p.data().get_idx_version();
 207       write!(f, "{}{}", c, idx)
 208     }
 209   }
 210
 211   #[derive(Debug)]
 212   struct State {
 213     todo: Vec<Can>,
 214     can: Vec<Can>,
 215   }
 216
 217   const NPIECES: usize = 4;
 218   const DEPTH: usize = 7;
 219
 220   impl State {
 221     fn implement(&self) {
 222       eprintln!("implement {:?}", self);
 223       let mut notches: Notches = default();
 224       let mut pieces = SecondarySlotMap::new();
 225       for op in &self.todo { match op {
 226         &Can::Insert(p) => {
 227           let notch = notches.insert(Generation(0), p);
 228           notches.check();
 229           pieces.insert(p, notch);
 230         },
 231         &Can::Remove(p) => {
 232           let notch = pieces[p];
 233           notches.remove(p, notch).unwrap();
 234           notches.check();
 235         },
 236       }}
 237     }
 238
 239     fn recurse(&mut self) {
 240       if self.todo.len() == DEPTH { self.implement(); return; }
 241       eprintln!("  recurse {:?}", &self);
 242
 243       for i in 0..self.can.len() {
 244         let op = self.can.swap_remove(i);
 245
 246         let l = self.can.len();
 247         match &op {
 248           &Can::Insert(p) => { self.can.push(Can::Remove(p)) },
 249           &Can::Remove(_) => { },
 250         }
 251
 252         self.todo.push(op);
 253         self.recurse();
 254         let op = self.todo.pop().unwrap();
 255
 256         self.can.truncate(l);
 257
 258         let last = if i < self.can.len() {
 259           mem::replace(&mut self.can[i], op)
 260         } else {
 261           op
 262         };
 263         self.can.push(last);
 264       }
 265     }
 266   }
 267
 268
 269   let mut st = State {
 270     todo: vec![],
 271     can: {
 272       let mut slotmap: DenseSlotMap<PieceId,()> = default();
 273       (0..NPIECES)
 274         .map(|_| slotmap.insert(()))
 275         .map(|p| Can::Insert(p))
 276         .collect()
 277     },
 278   };
 279
 280   st.recurse();
 281 }
 282
 283 pub fn permute(_occid: OccId,
 284                occ: &mut Occultation,
 285                gplayers: &mut GPlayers,
 286                gpieces: &mut GPieces,
 287                ipieces: &IPieces) {
 288   let new_notches = {
 289
 290     let mut ilks: HashMap<OccultIlkId, (
 291       Vec<Notch>,
 292       Vec<PieceId>,
 293     )> = HashMap::new();
 294
 295     for (notch, nr) in occ.notches.table.iter_enumerated() {
 296       let piece = if let Some(p) = nr.piece() { p } else { continue };
 297       if_let!{ Some(gpc) = gpieces.get(piece); else continue }
 298       if gpc.held.is_some() { continue }
 299       let occilk = (|| Some(ipieces.get(piece)?.occilk.as_ref()?))();
 300       if_let!{ Some(occilk) = occilk; else { continue; }}
 301       if_let!{ IOI::Mix(occilk) = occilk; else continue; }
 302       let (notches, pieces) = ilks.entry(*occilk.borrow()).or_default();
 303       notches.push(notch);
 304       pieces.push(piece);
 305     }
 306
 307     let mut new_notches = occ.notches.table.clone();
 308     for (_occilk, (notches, pieces)) in ilks {
 309       // We must permute for if we have any views that are scrambled
 310       // or displaced obviously.  For invisible too, so that when they
 311       // reappear the ids have been permuted.  And that's all the
 312       // non-Visible views which an occultation ought to have at least
 313       // one of...
 314       //
 315       // We choose a single permutation of each of the subsets (for a
 316       // partiular ilk) of the pieces in the Occultation::notches.
 317
 318       let permu = {
 319         let mut permu = pieces;
 320         config().game_rng.shuffle(&mut permu);
 321         permu
 322       };
 323
 324       for (notch, new_piece) in itertools::zip_eq(notches, permu) {
 325         new_notches[notch] = NR::Piece(new_piece);
 326         gpieces.get_mut(new_piece).unwrap()
 327           .occult.passive.as_mut().unwrap()
 328           .permute_notch
 329           = Some(notch);
 330       }
 331     }
 332
 333     new_notches
 334   };
 335
 336   for (player, gpl) in gplayers.iter_mut() {
 337     match occ.views.get_kind(player) {
 338       OccK::Visible => continue,
 339       OccK::Scrambled |
 340       OccK::Displaced{..} |
 341       OccK::Invisible => (),
 342     };
 343
 344     let mut fwd_updates = vec![];
 345     for (old, new) in izip!(&occ.notches.table, &new_notches) {
 346       if_chain! {
 347         if let Some((old, new)) = zip_eq(old.piece(), new.piece()).next();
 348         if let Some(vpid) = gpl.idmap.fwd(old);
 349         then {
 350           fwd_updates.push((new, vpid));
 351           if let Some(e) = gpl.idmap.r.get_mut(vpid) {
 352             *e = new;
 353           }
 354         }
 355       }
 356     }
 357
 358     for (new, vpid) in fwd_updates {
 359       gpl.idmap.f.insert(new, vpid);
 360     }
 361
 362   }
 363   occ.notches.table = new_notches;
 364   trace_dbg!("permuted", &occ);
 365 }
 366
 367 #[cfg(not(debug_assertions))]
 368 #[inline]
 369 pub fn consistency_check(
 370   _gplayers: &GPlayers,
 371   _gpieces: &GPieces,
 372   _goccults: &GOccults,
 373 ) { }
 374
 375 #[cfg(debug_assertions)]
 376 pub fn consistency_check(
 377   gplayers: &GPlayers,
 378   gpieces: &GPieces,
 379   goccults: &GOccults,
 380 ) {
 381   for (_player, gpl) in gplayers.iter() {
 382     for (piece, &vpid) in gpl.idmap.f.iter() {
 383       if let Some(&rpiece) = gpl.idmap.r.get(vpid) {
 384         assert_eq!(piece, rpiece);
 385       }
 386     }
 387     for (vpid, &piece) in gpl.idmap.r.iter() {
 388       if let Some(&fvpid) = gpl.idmap.f.get(piece) {
 389         assert_eq!(vpid, fvpid);
 390       }
 391     }
 392   }
 393
 394   for (piece, gpc) in gpieces.iter() {
 395     if let Some(occid) = gpc.occult.active {
 396       let occ = goccults.occults.get(occid).unwrap();
 397       assert_eq!(occ.occulter, piece);
 398       assert_eq!(&gpc.occult.passive, &None);
 399     }
 400
 401     if let Some(Passive { occid, permute_notch }) = gpc.occult.passive {
 402       let occ = goccults.occults.get(occid).unwrap();
 403       if let Some(notch) = permute_notch {
 404         assert_eq!(occ.notches.table[notch], NR::Piece(piece));
 405       } else {
 406         assert!(occ.unnotched.contains(&piece));
 407       }
 408     }
 409   }
 410
 411   for (occid, occ) in goccults.occults.iter() {
 412     let ogpc = gpieces.get(occ.occulter).unwrap();
 413     assert_eq!(ogpc.occult.active, Some(occid));
 414     assert_eq!(occ.notches.table.len(), occ.notches.zg.len());
 415
 416     for (notch, nr) in occ.notches.table.iter_enumerated() {
 417       if_let!{ Some(ppiece) = nr.piece(); else continue };
 418       let pgpc = gpieces.get(ppiece).unwrap();
 419       let passive = pgpc.occult.passive.as_ref().unwrap();
 420       assert_eq!(passive.occid, occid);
 421       assert_eq!(passive.permute_notch.unwrap(), notch);
 422     }
 423
 424     let nfree1 = occ.notches.table.iter()
 425       .filter(|nr| nr.piece().is_none()).count();
 426     let mut walk = occ.notches.freelist;
 427     let mut nfree2 = 0;
 428     while let Some(here) = walk {
 429       nfree2 += 1;
 430       let next = match occ.notches.table[here] {
 431         NR::Free(next) => next,
 432         NR::Piece(_) => panic!(),
 433       };
 434       if let Some(next) = next {
 435         assert!(next > here);
 436       }
 437       walk = next;
 438     }
 439     assert_eq!(nfree1,  nfree2);
 440
 441     for &ppiece in &occ.unnotched {
 442       assert_eq!(gpieces.get(ppiece).unwrap().occult.passive,
 443                  Some(Passive { occid, permute_notch: None }));
 444     }
 445   }
 446 }
 447