slots.rs 58.4 KB
Newer Older
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1
// Copyright 2019-2020 Parity Technologies (UK) Ltd.
Gavin Wood's avatar
Gavin Wood committed
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// This file is part of Polkadot.

// Polkadot is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// Polkadot is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.

//! Auctioning system to determine the set of Parachains in operation. This includes logic for the
//! auctioning mechanism, for locking balance as part of the "payment", and to provide the requisite
//! information for commissioning and decommissioning them.

21
use sp_std::{prelude::*, mem::swap, convert::TryInto};
22
use sp_runtime::traits::{
23
24
	CheckedSub, StaticLookup, Zero, One, CheckedConversion, Hash, AccountIdConversion,
};
25
use frame_support::weights::SimpleDispatchInfo;
26
use codec::{Encode, Decode, Codec};
27
use frame_support::{
28
	decl_module, decl_storage, decl_event, decl_error, ensure, dispatch::DispatchResult,
29
	traits::{Currency, ReservableCurrency, WithdrawReason, ExistenceRequirement, Get, Randomness},
30
};
31
32
33
use primitives::parachain::{
	SwapAux, PARACHAIN_INFO, Id as ParaId
};
34
use system::{ensure_signed, ensure_root};
35
use crate::registrar::{Registrar, swap_ordered_existence};
Gavin Wood's avatar
Gavin Wood committed
36
37
38
39
40
41
42
43
44
45
46
47
48
use crate::slot_range::{SlotRange, SLOT_RANGE_COUNT};

type BalanceOf<T> = <<T as Trait>::Currency as Currency<<T as system::Trait>::AccountId>>::Balance;

/// The module's configuration trait.
pub trait Trait: system::Trait {
	/// The overarching event type.
	type Event: From<Event<Self>> + Into<<Self as system::Trait>::Event>;

	/// The currency type used for bidding.
	type Currency: ReservableCurrency<Self::AccountId>;

	/// The parachain registrar type.
49
	type Parachains: Registrar<Self::AccountId>;
Gavin Wood's avatar
Gavin Wood committed
50
51
52
53
54
55

	/// The number of blocks over which an auction may be retroactively ended.
	type EndingPeriod: Get<Self::BlockNumber>;

	/// The number of blocks over which a single period lasts.
	type LeasePeriod: Get<Self::BlockNumber>;
56
57
58

	/// Something that provides randomness in the runtime.
	type Randomness: Randomness<Self::Hash>;
Gavin Wood's avatar
Gavin Wood committed
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
}

/// A sub-bidder identifier. Used to distinguish between different logical bidders coming from the
/// same account ID.
pub type SubId = u32;
/// An auction index. We count auctions in this type.
pub type AuctionIndex = u32;

/// A bidder identifier, which is just the combination of an account ID and a sub-bidder ID.
/// This is called `NewBidder` in order to distinguish between bidders that would deploy a *new*
/// parachain and pre-existing parachains bidding to renew themselves.
#[derive(Clone, Eq, PartialEq, Encode, Decode)]
#[cfg_attr(feature = "std", derive(Debug))]
pub struct NewBidder<AccountId> {
	/// The bidder's account ID; this is the account that funds the bid.
74
	pub who: AccountId,
Gavin Wood's avatar
Gavin Wood committed
75
76
	/// An additional ID to allow the same account ID (and funding source) to have multiple
	/// logical bidders.
77
	pub sub: SubId,
Gavin Wood's avatar
Gavin Wood committed
78
79
80
81
82
}

/// The desired target of a bidder in an auction.
#[derive(Clone, Eq, PartialEq, Encode, Decode)]
#[cfg_attr(feature = "std", derive(Debug))]
83
pub enum Bidder<AccountId> {
Gavin Wood's avatar
Gavin Wood committed
84
85
86
87
88
89
90
91
	/// An account ID, funds coming from that account.
	New(NewBidder<AccountId>),

	/// An existing parachain, funds coming from the amount locked as part of a previous bid topped
	/// up with funds administered by the parachain.
	Existing(ParaId),
}

92
impl<AccountId: Clone + Default + Codec> Bidder<AccountId> {
Gavin Wood's avatar
Gavin Wood committed
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
	/// Get the account that will fund this bid.
	fn funding_account(&self) -> AccountId {
		match self {
			Bidder::New(new_bidder) => new_bidder.who.clone(),
			Bidder::Existing(para_id) => para_id.into_account(),
		}
	}
}

/// Information regarding a parachain that will be deployed.
///
/// We store either the bidder that will be able to set the final deployment information or the
/// information itself.
#[derive(Clone, Eq, PartialEq, Encode, Decode)]
#[cfg_attr(feature = "std", derive(Debug))]
pub enum IncomingParachain<AccountId, Hash> {
	/// Deploy information not yet set; just the bidder identity.
	Unset(NewBidder<AccountId>),
111
112
113
114
115
116
	/// Deploy information set only by code hash; so we store the code hash, code size, and head data.
	///
	/// The code size must be included so that checks against a maximum code size
	/// can be done. If the size of the preimage of the code hash does not match
	/// the given code size, it will not be possible to register the parachain.
	Fixed { code_hash: Hash, code_size: u32, initial_head_data: Vec<u8> },
Gavin Wood's avatar
Gavin Wood committed
117
118
119
120
121
122
	/// Deploy information fully set; so we store the code and head data.
	Deploy { code: Vec<u8>, initial_head_data: Vec<u8> },
}

type LeasePeriodOf<T> = <T as system::Trait>::BlockNumber;
// Winning data type. This encodes the top bidders of each range together with their bid.
123
124
type WinningData<T> =
	[Option<(Bidder<<T as system::Trait>::AccountId>, BalanceOf<T>)>; SLOT_RANGE_COUNT];
Gavin Wood's avatar
Gavin Wood committed
125
126
// Winners data type. This encodes each of the final winners of a parachain auction, the parachain
// index assigned to them, their winning bid and the range that they won.
127
128
type WinnersData<T> =
	Vec<(Option<NewBidder<<T as system::Trait>::AccountId>>, ParaId, BalanceOf<T>, SlotRange)>;
Gavin Wood's avatar
Gavin Wood committed
129

130
// This module's storage items.
Gavin Wood's avatar
Gavin Wood committed
131
132
decl_storage! {
	trait Store for Module<T: Trait> as Slots {
Leo Arias's avatar
Leo Arias committed
133
		/// The number of auctions that have been started so far.
134
		pub AuctionCounter get(fn auction_counter): AuctionIndex;
Gavin Wood's avatar
Gavin Wood committed
135

136
137
		/// Ordered list of all `ParaId` values that are managed by this module. This includes
		/// chains that are not yet deployed (but have won an auction in the future).
138
		pub ManagedIds get(fn managed_ids): Vec<ParaId>;
Gavin Wood's avatar
Gavin Wood committed
139
140
141
142
143
144
145
146
147
148
149
150
151
152

		/// Various amounts on deposit for each parachain. An entry in `ManagedIds` implies a non-
		/// default entry here.
		///
		/// The actual amount locked on its behalf at any time is the maximum item in this list. The
		/// first item in the list is the amount locked for the current Lease Period. Following
		/// items are for the subsequent lease periods.
		///
		/// The default value (an empty list) implies that the parachain no longer exists (or never
		/// existed) as far as this module is concerned.
		///
		/// If a parachain doesn't exist *yet* but is scheduled to exist in the future, then it
		/// will be left-padded with one or more zeroes to denote the fact that nothing is held on
		/// deposit for the non-existent chain currently, but is held at some point in the future.
153
		pub Deposits get(fn deposits): map hasher(twox_64_concat) ParaId => Vec<BalanceOf<T>>;
Gavin Wood's avatar
Gavin Wood committed
154
155
156
157
158
159

		/// Information relating to the current auction, if there is one.
		///
		/// The first item in the tuple is the lease period index that the first of the four
		/// contiguous lease periods on auction is for. The second is the block number when the
		/// auction will "begin to end", i.e. the first block of the Ending Period of the auction.
160
		pub AuctionInfo get(fn auction_info): Option<(LeasePeriodOf<T>, T::BlockNumber)>;
Gavin Wood's avatar
Gavin Wood committed
161
162
163
164

		/// The winning bids for each of the 10 ranges at each block in the final Ending Period of
		/// the current auction. The map's key is the 0-based index into the Ending Period. The
		/// first block of the ending period is 0; the last is `EndingPeriod - 1`.
165
		pub Winning get(fn winning): map hasher(twox_64_concat) T::BlockNumber => Option<WinningData<T>>;
Gavin Wood's avatar
Gavin Wood committed
166
167
168

		/// Amounts currently reserved in the accounts of the bidders currently winning
		/// (sub-)ranges.
169
		pub ReservedAmounts get(fn reserved_amounts):
170
			map hasher(twox_64_concat) Bidder<T::AccountId> => Option<BalanceOf<T>>;
Gavin Wood's avatar
Gavin Wood committed
171
172
173

		/// The set of Para IDs that have won and need to be on-boarded at an upcoming lease-period.
		/// This is cleared out on the first block of the lease period.
174
		pub OnboardQueue get(fn onboard_queue): map hasher(twox_64_concat) LeasePeriodOf<T> => Vec<ParaId>;
Gavin Wood's avatar
Gavin Wood committed
175
176
177
178
179

		/// The actual on-boarding information. Only exists when one of the following is true:
		/// - It is before the lease period that the parachain should be on-boarded.
		/// - The full on-boarding information has not yet been provided and the parachain is not
		/// yet due to be off-boarded.
180
		pub Onboarding get(fn onboarding):
181
			map hasher(twox_64_concat) ParaId =>
Gavin Wood's avatar
Gavin Wood committed
182
183
184
185
			Option<(LeasePeriodOf<T>, IncomingParachain<T::AccountId, T::Hash>)>;

		/// Off-boarding account; currency held on deposit for the parachain gets placed here if the
		/// parachain gets off-boarded; i.e. its lease period is up and it isn't renewed.
186
		pub Offboarding get(fn offboarding): map hasher(twox_64_concat) ParaId => T::AccountId;
187
188
189
190
191
	}
}

impl<T: Trait> SwapAux for Module<T> {
	fn ensure_can_swap(one: ParaId, other: ParaId) -> Result<(), &'static str> {
192
		if <Onboarding<T>>::contains_key(one) || <Onboarding<T>>::contains_key(other) {
193
194
195
196
197
198
199
200
201
			Err("can't swap an undeployed parachain")?
		}
		Ok(())
	}
	fn on_swap(one: ParaId, other: ParaId) -> Result<(), &'static str> {
		<Offboarding<T>>::swap(one, other);
		<Deposits<T>>::swap(one, other);
		ManagedIds::mutate(|ids| swap_ordered_existence(ids, one, other));
		Ok(())
Gavin Wood's avatar
Gavin Wood committed
202
203
204
205
206
207
208
209
	}
}

decl_event!(
	pub enum Event<T> where
		AccountId = <T as system::Trait>::AccountId,
		BlockNumber = <T as system::Trait>::BlockNumber,
		LeasePeriod = LeasePeriodOf<T>,
210
		ParaId = ParaId,
Gavin Wood's avatar
Gavin Wood committed
211
212
213
214
215
216
217
218
219
220
221
222
		Balance = BalanceOf<T>,
	{
		/// A new lease period is beginning.
		NewLeasePeriod(LeasePeriod),
		/// An auction started. Provides its index and the block number where it will begin to
		/// close and the first lease period of the quadruplet that is auctioned.
		AuctionStarted(AuctionIndex, LeasePeriod, BlockNumber),
		/// An auction ended. All funds become unreserved.
		AuctionClosed(AuctionIndex),
		/// Someone won the right to deploy a parachain. Balance amount is deducted for deposit.
		WonDeploy(NewBidder<AccountId>, SlotRange, ParaId, Balance),
		/// An existing parachain won the right to continue.
223
		/// First balance is the extra amount reseved. Second is the total amount reserved.
Gavin Wood's avatar
Gavin Wood committed
224
225
226
227
228
229
230
231
232
		WonRenewal(ParaId, SlotRange, Balance, Balance),
		/// Funds were reserved for a winning bid. First balance is the extra amount reserved.
		/// Second is the total.
		Reserved(AccountId, Balance, Balance),
		/// Funds were unreserved since bidder is no longer active.
		Unreserved(AccountId, Balance),
	}
);

233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
decl_error! {
	pub enum Error for Module<T: Trait> {
		/// This auction is already in progress.
		AuctionInProgress,
		/// The lease period is in the past.
		LeasePeriodInPast,
		/// The origin for this call must be a parachain.
		NotParaOrigin,
		/// The parachain ID is not onboarding.
		ParaNotOnboarding,
		/// The origin for this call must be the origin who registered the parachain.
		InvalidOrigin,
		/// Parachain is already registered.
		AlreadyRegistered,
		/// The code must correspond to the hash.
		InvalidCode,
		/// Deployment data has not been set for this parachain.
		UnsetDeployData,
		/// The bid must overlap all intersecting ranges.
		NonIntersectingRange,
		/// Not a current auction.
		NotCurrentAuction,
		/// Not an auction.
		NotAuction,
257
258
259
260
		/// Given code size is too large.
		CodeTooLarge,
		/// Given initial head data is too large.
		HeadDataTooLarge,
261
262
263
	}
}

Gavin Wood's avatar
Gavin Wood committed
264
265
decl_module! {
	pub struct Module<T: Trait> for enum Call where origin: T::Origin {
266
267
		type Error = Error<T>;

thiolliere's avatar
thiolliere committed
268
		fn deposit_event() = default;
Gavin Wood's avatar
Gavin Wood committed
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294

		fn on_initialize(n: T::BlockNumber) {
			let lease_period = T::LeasePeriod::get();
			let lease_period_index: LeasePeriodOf<T> = (n / lease_period).into();

			// Check to see if an auction just ended.
			if let Some((winning_ranges, auction_lease_period_index)) = Self::check_auction_end(n) {
				// Auction is ended now. We have the winning ranges and the lease period index which
				// acts as the offset. Handle it.
				Self::manage_auction_end(
					lease_period_index,
					auction_lease_period_index,
					winning_ranges,
				);
			}
			// If we're beginning a new lease period then handle that, too.
			if (n % lease_period).is_zero() {
				Self::manage_lease_period_start(lease_period_index);
			}
		}

		fn on_finalize(now: T::BlockNumber) {
			// If the current auction is in it ending period, then ensure that the (sub-)range
			// winner information is duplicated from the previous block in case no bids happened
			// in this block.
			if let Some(offset) = Self::is_ending(now) {
295
				if !<Winning<T>>::contains_key(&offset) {
Gavin Wood's avatar
Gavin Wood committed
296
297
298
299
300
301
302
303
304
305
306
307
308
309
					<Winning<T>>::insert(offset,
						offset.checked_sub(&One::one())
							.and_then(<Winning<T>>::get)
							.unwrap_or_default()
					);
				}
			}
		}

		/// Create a new auction.
		///
		/// This can only happen when there isn't already an auction in progress and may only be
		/// called by the root origin. Accepts the `duration` of this auction and the
		/// `lease_period_index` of the initial lease period of the four that are to be auctioned.
310
		#[weight = SimpleDispatchInfo::FixedOperational(100_000)]
311
		pub fn new_auction(origin,
Gavin Wood's avatar
Gavin Wood committed
312
313
314
			#[compact] duration: T::BlockNumber,
			#[compact] lease_period_index: LeasePeriodOf<T>
		) {
315
			ensure_root(origin)?;
316
317
			ensure!(!Self::is_in_progress(), Error::<T>::AuctionInProgress);
			ensure!(lease_period_index >= Self::lease_period_index(), Error::<T>::LeasePeriodInPast);
Gavin Wood's avatar
Gavin Wood committed
318
319

			// Bump the counter.
Gavin Wood's avatar
Gavin Wood committed
320
			let n = <AuctionCounter>::mutate(|n| { *n += 1; *n });
Gavin Wood's avatar
Gavin Wood committed
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344

			// Set the information.
			let ending = <system::Module<T>>::block_number() + duration;
			<AuctionInfo<T>>::put((lease_period_index, ending));

			Self::deposit_event(RawEvent::AuctionStarted(n, lease_period_index, ending))
		}

		/// Make a new bid from an account (including a parachain account) for deploying a new
		/// parachain.
		///
		/// Multiple simultaneous bids from the same bidder are allowed only as long as all active
		/// bids overlap each other (i.e. are mutually exclusive). Bids cannot be redacted.
		///
		/// - `sub` is the sub-bidder ID, allowing for multiple competing bids to be made by (and
		/// funded by) the same account.
		/// - `auction_index` is the index of the auction to bid on. Should just be the present
		/// value of `AuctionCounter`.
		/// - `first_slot` is the first lease period index of the range to bid on. This is the
		/// absolute lease period index value, not an auction-specific offset.
		/// - `last_slot` is the last lease period index of the range to bid on. This is the
		/// absolute lease period index value, not an auction-specific offset.
		/// - `amount` is the amount to bid to be held as deposit for the parachain should the
		/// bid win. This amount is held throughout the range.
345
		#[weight = SimpleDispatchInfo::FixedNormal(500_000)]
346
		pub fn bid(origin,
Gavin Wood's avatar
Gavin Wood committed
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
			#[compact] sub: SubId,
			#[compact] auction_index: AuctionIndex,
			#[compact] first_slot: LeasePeriodOf<T>,
			#[compact] last_slot: LeasePeriodOf<T>,
			#[compact] amount: BalanceOf<T>
		) {
			let who = ensure_signed(origin)?;
			let bidder = Bidder::New(NewBidder{who: who.clone(), sub});
			Self::handle_bid(bidder, auction_index, first_slot, last_slot, amount)?;
		}

		/// Make a new bid from a parachain account for renewing that (pre-existing) parachain.
		///
		/// The origin *must* be a parachain account.
		///
		/// Multiple simultaneous bids from the same bidder are allowed only as long as all active
		/// bids overlap each other (i.e. are mutually exclusive). Bids cannot be redacted.
		///
		/// - `auction_index` is the index of the auction to bid on. Should just be the present
		/// value of `AuctionCounter`.
		/// - `first_slot` is the first lease period index of the range to bid on. This is the
		/// absolute lease period index value, not an auction-specific offset.
		/// - `last_slot` is the last lease period index of the range to bid on. This is the
		/// absolute lease period index value, not an auction-specific offset.
		/// - `amount` is the amount to bid to be held as deposit for the parachain should the
		/// bid win. This amount is held throughout the range.
373
		#[weight = SimpleDispatchInfo::FixedNormal(500_000)]
374
		fn bid_renew(origin,
Gavin Wood's avatar
Gavin Wood committed
375
376
377
378
379
380
			#[compact] auction_index: AuctionIndex,
			#[compact] first_slot: LeasePeriodOf<T>,
			#[compact] last_slot: LeasePeriodOf<T>,
			#[compact] amount: BalanceOf<T>
		) {
			let who = ensure_signed(origin)?;
381
			let para_id = <ParaId>::try_from_account(&who)
382
				.ok_or(Error::<T>::NotParaOrigin)?;
Gavin Wood's avatar
Gavin Wood committed
383
384
385
386
387
388
389
390
391
			let bidder = Bidder::Existing(para_id);
			Self::handle_bid(bidder, auction_index, first_slot, last_slot, amount)?;
		}

		/// Set the off-boarding information for a parachain.
		///
		/// The origin *must* be a parachain account.
		///
		/// - `dest` is the destination account to receive the parachain's deposit.
392
		#[weight = SimpleDispatchInfo::FixedNormal(1_000_000)]
393
		pub fn set_offboarding(origin, dest: <T::Lookup as StaticLookup>::Source) {
Gavin Wood's avatar
Gavin Wood committed
394
395
			let who = ensure_signed(origin)?;
			let dest = T::Lookup::lookup(dest)?;
396
			let para_id = <ParaId>::try_from_account(&who)
397
				.ok_or(Error::<T>::NotParaOrigin)?;
Gavin Wood's avatar
Gavin Wood committed
398
399
400
401
402
403
404
405
406
407
			<Offboarding<T>>::insert(para_id, dest);
		}

		/// Set the deploy information for a successful bid to deploy a new parachain.
		///
		/// - `origin` must be the successful bidder account.
		/// - `sub` is the sub-bidder ID of the bidder.
		/// - `para_id` is the parachain ID allotted to the winning bidder.
		/// - `code_hash` is the hash of the parachain's Wasm validation function.
		/// - `initial_head_data` is the parachain's initial head data.
408
		#[weight = SimpleDispatchInfo::FixedNormal(500_000)]
409
		pub fn fix_deploy_data(origin,
Gavin Wood's avatar
Gavin Wood committed
410
			#[compact] sub: SubId,
411
			#[compact] para_id: ParaId,
Gavin Wood's avatar
Gavin Wood committed
412
			code_hash: T::Hash,
413
			code_size: u32,
Gavin Wood's avatar
Gavin Wood committed
414
415
416
417
			initial_head_data: Vec<u8>
		) {
			let who = ensure_signed(origin)?;
			let (starts, details) = <Onboarding<T>>::get(&para_id)
418
				.ok_or(Error::<T>::ParaNotOnboarding)?;
Gavin Wood's avatar
Gavin Wood committed
419
			if let IncomingParachain::Unset(ref nb) = details {
420
				ensure!(nb.who == who && nb.sub == sub, Error::<T>::InvalidOrigin);
Gavin Wood's avatar
Gavin Wood committed
421
			} else {
422
				Err(Error::<T>::AlreadyRegistered)?
Gavin Wood's avatar
Gavin Wood committed
423
			}
424
425
426
427
428
429
430
431
432
433
434

			ensure!(
				T::Parachains::head_data_size_allowed(initial_head_data.len() as _),
				Error::<T>::HeadDataTooLarge,
			);
			ensure!(
				T::Parachains::code_size_allowed(code_size),
				Error::<T>::CodeTooLarge,
			);

			let item = (starts, IncomingParachain::Fixed{code_hash, code_size, initial_head_data});
Gavin Wood's avatar
Gavin Wood committed
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
			<Onboarding<T>>::insert(&para_id, item);
		}

		/// Note a new parachain's code.
		///
		/// This must be called after `fix_deploy_data` and `code` must be the preimage of the
		/// `code_hash` passed there for the same `para_id`.
		///
		/// This may be called before or after the beginning of the parachain's first lease period.
		/// If called before then the parachain will become active at the first block of its
		/// starting lease period. If after, then it will become active immediately after this call.
		///
		/// - `_origin` is irrelevant.
		/// - `para_id` is the parachain ID whose code will be elaborated.
		/// - `code` is the preimage of the registered `code_hash` of `para_id`.
450
		#[weight = SimpleDispatchInfo::FixedNormal(5_000_000)]
451
		pub fn elaborate_deploy_data(_origin, #[compact] para_id: ParaId, code: Vec<u8>) -> DispatchResult {
Gavin Wood's avatar
Gavin Wood committed
452
			let (starts, details) = <Onboarding<T>>::get(&para_id)
453
				.ok_or(Error::<T>::ParaNotOnboarding)?;
454
455
			if let IncomingParachain::Fixed{code_hash, code_size, initial_head_data} = details {
				ensure!(code.len() as u32 == code_size, Error::<T>::InvalidCode);
456
				ensure!(<T as system::Trait>::Hashing::hash(&code) == code_hash, Error::<T>::InvalidCode);
457

Gavin Wood's avatar
Gavin Wood committed
458
459
460
461
462
463
464
465
				if starts > Self::lease_period_index() {
					// Hasn't yet begun. Replace the on-boarding entry with the new information.
					let item = (starts, IncomingParachain::Deploy{code, initial_head_data});
					<Onboarding<T>>::insert(&para_id, item);
				} else {
					// Should have already begun. Remove the on-boarding entry and register the
					// parachain for its immediate start.
					<Onboarding<T>>::remove(&para_id);
466
467
					let _ = T::Parachains::
						register_para(para_id, PARACHAIN_INFO, code, initial_head_data);
Gavin Wood's avatar
Gavin Wood committed
468
				}
469
470

				Ok(())
Gavin Wood's avatar
Gavin Wood committed
471
			} else {
472
				Err(Error::<T>::UnsetDeployData)?
Gavin Wood's avatar
Gavin Wood committed
473
474
475
476
477
478
479
			}
		}
	}
}

impl<T: Trait> Module<T> {
	/// Deposit currently held for a particular parachain that we administer.
480
	fn deposit_held(para_id: &ParaId) -> BalanceOf<T> {
Gavin Wood's avatar
Gavin Wood committed
481
482
483
484
		<Deposits<T>>::get(para_id).into_iter().max().unwrap_or_else(Zero::zero)
	}

	/// True if an auction is in progress.
485
	pub fn is_in_progress() -> bool {
Gavin Wood's avatar
Gavin Wood committed
486
487
488
489
490
		<AuctionInfo<T>>::exists()
	}

	/// Returns `Some(n)` if the now block is part of the ending period of an auction, where `n`
	/// represents how far into the ending period this block is. Otherwise, returns `None`.
491
	pub fn is_ending(now: T::BlockNumber) -> Option<T::BlockNumber> {
Gavin Wood's avatar
Gavin Wood committed
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
		if let Some((_, early_end)) = <AuctionInfo<T>>::get() {
			if let Some(after_early_end) = now.checked_sub(&early_end) {
				if after_early_end < T::EndingPeriod::get() {
					return Some(after_early_end)
				}
			}
		}
		None
	}

	/// Returns the current lease period.
	fn lease_period_index() -> LeasePeriodOf<T> {
		(<system::Module<T>>::block_number() / T::LeasePeriod::get()).into()
	}

	/// Some when the auction's end is known (with the end block number). None if it is unknown.
	/// If `Some` then the block number must be at most the previous block and at least the
	/// previous block minus `T::EndingPeriod::get()`.
	///
	/// This mutates the state, cleaning up `AuctionInfo` and `Winning` in the case of an auction
	/// ending. An immediately subsequent call with the same argument will always return `None`.
	fn check_auction_end(now: T::BlockNumber) -> Option<(WinningData<T>, LeasePeriodOf<T>)> {
		if let Some((lease_period_index, early_end)) = <AuctionInfo<T>>::get() {
			if early_end + T::EndingPeriod::get() == now {
				// Just ended!
				let ending_period = T::EndingPeriod::get();
518
				let offset = T::BlockNumber::decode(&mut T::Randomness::random_seed().as_ref())
Gavin Wood's avatar
Gavin Wood committed
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
					.expect("secure hashes always bigger than block numbers; qed") % ending_period;
				let res = <Winning<T>>::get(offset).unwrap_or_default();
				let mut i = T::BlockNumber::zero();
				while i < ending_period {
					<Winning<T>>::remove(i);
					i += One::one();
				}
				<AuctionInfo<T>>::kill();
				return Some((res, lease_period_index))
			}
		}
		None
	}

	/// Auction just ended. We have the current lease period, the auction's lease period (which
	/// is guaranteed to be at least the current period) and the bidders that were winning each
	/// range at the time of the auction's close.
	fn manage_auction_end(
		lease_period_index: LeasePeriodOf<T>,
		auction_lease_period_index: LeasePeriodOf<T>,
		winning_ranges: WinningData<T>,
	) {
		// First, unreserve all amounts that were reserved for the bids. We will later deduct the
		// amounts from the bidders that ended up being assigned the slot so there's no need to
		// special-case them here.
		for (bidder, _) in winning_ranges.iter().filter_map(|x| x.as_ref()) {
			if let Some(amount) = <ReservedAmounts<T>>::take(bidder) {
				T::Currency::unreserve(&bidder.funding_account(), amount);
			}
		}

		// Next, calculate the winning combination of slots and thus the final winners of the
		// auction.
		let winners = Self::calculate_winners(winning_ranges, T::Parachains::new_id);

		Self::deposit_event(RawEvent::AuctionClosed(Self::auction_counter()));

		// Go through those winners and deduct their bid, updating our table of deposits
		// accordingly.
		for (maybe_new_deploy, para_id, amount, range) in winners.into_iter() {
			match maybe_new_deploy {
				Some(bidder) => {
					// For new deployments we ensure the full amount is deducted. This should always
					// succeed as we just unreserved the same amount above.
					if T::Currency::withdraw(
						&bidder.who,
						amount,
Gavin Wood's avatar
Gavin Wood committed
566
						WithdrawReason::Fee.into(),
Gavin Wood's avatar
Gavin Wood committed
567
568
569
570
571
572
						ExistenceRequirement::AllowDeath
					).is_err() {
						continue;
					}

					// Add para IDs of any chains that will be newly deployed to our set of managed
573
					// IDs.
574
575
576
577
578
579
580
581
					ManagedIds::mutate(|ids|
						if let Err(pos) = ids.binary_search(&para_id) {
							ids.insert(pos, para_id)
						} else {
							// This can't happen as it's a winner being newly
							// deployed and thus the para_id shouldn't already be being managed.
						}
					);
Gavin Wood's avatar
Gavin Wood committed
582
583
584
585
586
587
588
					Self::deposit_event(RawEvent::WonDeploy(bidder.clone(), range, para_id, amount));

					// Add a deployment record so we know to on-board them at the appropriate
					// juncture.
					let begin_offset = <LeasePeriodOf<T>>::from(range.as_pair().0 as u32);
					let begin_lease_period = auction_lease_period_index + begin_offset;
					<OnboardQueue<T>>::mutate(begin_lease_period, |starts| starts.push(para_id));
589
590
					// Add a default off-boarding account which matches the original bidder
					<Offboarding<T>>::insert(&para_id, &bidder.who);
Gavin Wood's avatar
Gavin Wood committed
591
592
593
594
595
596
597
598
599
600
601
602
					let entry = (begin_lease_period, IncomingParachain::Unset(bidder));
					<Onboarding<T>>::insert(&para_id, entry);
				}
				None => {
					// For renewals, reserve any extra on top of what we already have held
					// on deposit for their chain.
					let extra = if let Some(additional) =
						amount.checked_sub(&Self::deposit_held(&para_id))
					{
						if T::Currency::withdraw(
							&para_id.into_account(),
							additional,
Gavin Wood's avatar
Gavin Wood committed
603
							WithdrawReason::Fee.into(),
Gavin Wood's avatar
Gavin Wood committed
604
605
606
607
608
609
610
611
							ExistenceRequirement::AllowDeath
						).is_err() {
							continue;
						}
						additional
					} else {
						Default::default()
					};
612
					Self::deposit_event(RawEvent::WonRenewal(para_id, range, extra, amount));
Gavin Wood's avatar
Gavin Wood committed
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
				}
			}

			// Finally, we update the deposit held so it is `amount` for the new lease period
			// indices that were won in the auction.
			let maybe_offset = auction_lease_period_index
				.checked_sub(&lease_period_index)
				.and_then(|x| x.checked_into::<usize>());
			if let Some(offset) = maybe_offset {
				// Should always succeed; for it to fail it would mean we auctioned a lease period
				// that already ended.

				// The lease period index range (begin, end) that newly belongs to this parachain
				// ID. We need to ensure that it features in `Deposits` to prevent it from being
				// reaped too early (any managed parachain whose `Deposits` set runs low will be
				// removed).
				let pair = range.as_pair();
				let pair = (pair.0 as usize + offset, pair.1 as usize + offset);
				<Deposits<T>>::mutate(para_id, |d| {
					// Left-pad with zeroes as necessary.
					if d.len() < pair.0 {
						d.resize_with(pair.0, Default::default);
					}
					// Then place the deposit values for as long as the chain should exist.
					for i in pair.0 ..= pair.1 {
						if d.len() > i {
							// The chain bought the same lease period twice. Just take the maximum.
							d[i] = d[i].max(amount);
						} else if d.len() == i {
							d.push(amount);
						} else {
							unreachable!("earlier resize means it must be >= i; qed")
						}
					}
				});
			}
		}
	}

	/// A new lease period is beginning. We're at the start of the first block of it.
	///
	/// We need to on-board and off-board parachains as needed. We should also handle reducing/
	/// returning deposits.
	fn manage_lease_period_start(lease_period_index: LeasePeriodOf<T>) {
		Self::deposit_event(RawEvent::NewLeasePeriod(lease_period_index));
		// First, bump off old deposits and decommission any managed chains that are coming
		// to a close.
660
		ManagedIds::mutate(|ids| {
Gavin Wood's avatar
Gavin Wood committed
661
662
663
664
665
666
667
668
669
670
671
672
			let new = ids.drain(..).filter(|id| {
				let mut d = <Deposits<T>>::get(id);
				if !d.is_empty() {
					// ^^ should always be true, since we would have deleted the entry otherwise.

					if d.len() == 1 {
						// Just one entry, which corresponds to the now-ended lease period. Time
						// to decommission this chain.
						if <Onboarding<T>>::take(id).is_none() {
							// Only unregister it if it was actually registered in the first place.
							// If the on-boarding entry still existed, then it was never actually
							// commissioned.
673
							let _ = T::Parachains::deregister_para(id.clone());
Gavin Wood's avatar
Gavin Wood committed
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
						}
						// Return the full deposit to the off-boarding account.
						T::Currency::deposit_creating(&<Offboarding<T>>::take(id), d[0]);
						// Remove the now-empty deposits set and don't keep the ID around.
						<Deposits<T>>::remove(id);
						false
					} else {
						// The parachain entry is continuing into the next lease period.
						// We need to pop the first deposit entry, which corresponds to the now-
						// ended lease period.
						let outgoing = d[0];
						d.remove(0);
						<Deposits<T>>::insert(id, &d);
						// Then we need to get the new amount that should continue to be held on
						// deposit for the parachain.
						let new_held = d.into_iter().max().unwrap_or_default();
						// If this is less than what we were holding previously, then return it
						// to the parachain itself.
						if let Some(rebate) = outgoing.checked_sub(&new_held) {
							T::Currency::deposit_creating(
								&id.into_account(),
								rebate
							);
						}
						// We keep this entry around until the next lease period.
						true
					}
				} else {
					false
				}
			}).collect::<Vec<_>>();
			*ids = new;
		});

		// Deploy any new chains that are due to be commissioned.
		for para_id in <OnboardQueue<T>>::take(lease_period_index) {
			if let Some((_, IncomingParachain::Deploy{code, initial_head_data}))
				= <Onboarding<T>>::get(&para_id)
			{
				// The chain's deployment data is set; go ahead and register it, and remove the
				// now-redundant on-boarding entry.
715
716
				let _ = T::Parachains::
					register_para(para_id.clone(), PARACHAIN_INFO, code, initial_head_data);
Gavin Wood's avatar
Gavin Wood committed
717
718
719
720
721
722
723
724
725
726
727
728
729
730
				// ^^ not much we can do if it fails for some reason.
				<Onboarding<T>>::remove(para_id)
			}
		}
	}

	/// Actually place a bid in the current auction.
	///
	/// - `bidder`: The account that will be funding this bid.
	/// - `auction_index`: The auction index of the bid. For this to succeed, must equal
	/// the current value of `AuctionCounter`.
	/// - `first_slot`: The first lease period index of the range to be bid on.
	/// - `last_slot`: The last lease period index of the range to be bid on (inclusive).
	/// - `amount`: The total amount to be the bid for deposit over the range.
731
	pub fn handle_bid(
732
		bidder: Bidder<T::AccountId>,
Gavin Wood's avatar
Gavin Wood committed
733
734
735
736
		auction_index: u32,
		first_slot: LeasePeriodOf<T>,
		last_slot: LeasePeriodOf<T>,
		amount: BalanceOf<T>
737
	) -> DispatchResult {
Gavin Wood's avatar
Gavin Wood committed
738
		// Bidding on latest auction.
739
		ensure!(auction_index == <AuctionCounter>::get(), Error::<T>::NotCurrentAuction);
Gavin Wood's avatar
Gavin Wood committed
740
		// Assume it's actually an auction (this should never fail because of above).
741
		let (first_lease_period, _) = <AuctionInfo<T>>::get().ok_or(Error::<T>::NotAuction)?;
Gavin Wood's avatar
Gavin Wood committed
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762

		// Our range.
		let range = SlotRange::new_bounded(first_lease_period, first_slot, last_slot)?;
		// Range as an array index.
		let range_index = range as u8 as usize;
		// The offset into the auction ending set.
		let offset = Self::is_ending(<system::Module<T>>::block_number()).unwrap_or_default();
		// The current winning ranges.
		let mut current_winning = <Winning<T>>::get(offset)
			.or_else(|| offset.checked_sub(&One::one()).and_then(<Winning<T>>::get))
			.unwrap_or_default();
		// If this bid beat the previous winner of our range.
		if current_winning[range_index].as_ref().map_or(true, |last| amount > last.1) {
			// This must overlap with all existing ranges that we're winning on or it's invalid.
			ensure!(current_winning.iter()
				.enumerate()
				.all(|(i, x)| x.as_ref().map_or(true, |(w, _)|
					w != &bidder || range.intersects(i.try_into()
						.expect("array has SLOT_RANGE_COUNT items; index never reaches that value; qed")
					)
				)),
763
				Error::<T>::NonIntersectingRange,
Gavin Wood's avatar
Gavin Wood committed
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
			);

			// Ok; we are the new winner of this range - reserve the additional amount and record.

			// Get the amount already held on deposit on our behalf if this is a renewal bid from
			// an existing parachain.
			let deposit_held = if let Bidder::Existing(ref bidder_para_id) = bidder {
				Self::deposit_held(bidder_para_id)
			} else {
				Zero::zero()
			};
			// Get the amount already reserved in any prior and still active bids by us.
			let already_reserved =
				<ReservedAmounts<T>>::get(&bidder).unwrap_or_default() + deposit_held;
			// If these don't already cover the bid...
			if let Some(additional) = amount.checked_sub(&already_reserved) {
				// ...then reserve some more funds from their account, failing if there's not
				// enough funds.
				T::Currency::reserve(&bidder.funding_account(), additional)?;
				// ...and record the amount reserved.
				<ReservedAmounts<T>>::insert(&bidder, amount);

				Self::deposit_event(RawEvent::Reserved(
					bidder.funding_account(),
					additional,
					amount
				));
			}

			// Return any funds reserved for the previous winner if they no longer have any active
			// bids.
			let mut outgoing_winner = Some((bidder, amount));
			swap(&mut current_winning[range_index], &mut outgoing_winner);
			if let Some((who, _)) = outgoing_winner {
				if current_winning.iter()
					.filter_map(Option::as_ref)
					.all(|&(ref other, _)| other != &who)
				{
					// Previous bidder is no longer winning any ranges: unreserve their funds.
					if let Some(amount) = <ReservedAmounts<T>>::take(&who) {
						// It really should be reserved; there's not much we can do here on fail.
						let _ = T::Currency::unreserve(&who.funding_account(), amount);

						Self::deposit_event(RawEvent::Unreserved(who.funding_account(), amount));
					}
				}
			}
			// Update the range winner.
			<Winning<T>>::insert(offset, &current_winning);
		}
		Ok(())
	}

	/// Calculate the final winners from the winning slots.
	///
	/// This is a simple dynamic programming algorithm designed by Al, the original code is at:
	/// https://github.com/w3f/consensus/blob/master/NPoS/auctiondynamicthing.py
	fn calculate_winners(
		mut winning: WinningData<T>,
823
		new_id: impl Fn() -> ParaId
Gavin Wood's avatar
Gavin Wood committed
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
	) -> WinnersData<T> {
		let winning_ranges = {
			let mut best_winners_ending_at:
				[(Vec<SlotRange>, BalanceOf<T>); 4] = Default::default();
			let best_bid = |range: SlotRange| {
				winning[range as u8 as usize].as_ref()
					.map(|(_, amount)| *amount * (range.len() as u32).into())
			};
			for i in 0..4 {
				let r = SlotRange::new_bounded(0, 0, i as u32).expect("`i < 4`; qed");
				if let Some(bid) = best_bid(r) {
					best_winners_ending_at[i] = (vec![r], bid);
				}
				for j in 0..i {
					let r = SlotRange::new_bounded(0, j as u32 + 1, i as u32)
						.expect("`i < 4`; `j < i`; `j + 1 < 4`; qed");
					if let Some(mut bid) = best_bid(r) {
						bid += best_winners_ending_at[j].1;
						if bid > best_winners_ending_at[i].1 {
							let mut new_winners = best_winners_ending_at[j].0.clone();
							new_winners.push(r);
							best_winners_ending_at[i] = (new_winners, bid);
						}
					} else {
						if best_winners_ending_at[j].1 > best_winners_ending_at[i].1 {
							best_winners_ending_at[i] = best_winners_ending_at[j].clone();
						}
					}
				}
			}
			let [_, _, _, (winning_ranges, _)] = best_winners_ending_at;
			winning_ranges
		};

		winning_ranges.into_iter().map(|r| {
			let mut final_winner = (Bidder::Existing(Default::default()), Default::default());
			swap(&mut final_winner, winning[r as u8 as usize].as_mut()
				.expect("none values are filtered out in previous logic; qed"));
			let (slot_winner, bid) = final_winner;
			match slot_winner {
				Bidder::New(new_bidder) => (Some(new_bidder), new_id(), bid, r),
				Bidder::Existing(para_id) => (None, para_id, bid, r),
			}
		}).collect::<Vec<_>>()
	}
}

/// tests for this module
#[cfg(test)]
mod tests {
	use super::*;
875
	use std::{collections::HashMap, cell::RefCell};
Gavin Wood's avatar
Gavin Wood committed
876

877
878
	use sp_core::H256;
	use sp_runtime::{
879
		Perbill, testing::Header,
880
		traits::{BlakeTwo256, Hash, IdentityLookup, OnInitialize, OnFinalize},
Gavin Wood's avatar
Gavin Wood committed
881
	};
882
	use frame_support::{impl_outer_origin, parameter_types, assert_ok, assert_noop};
Gavin Wood's avatar
Gavin Wood committed
883
	use balances;
884
	use primitives::parachain::{Id as ParaId, Info as ParaInfo};
Gavin Wood's avatar
Gavin Wood committed
885
886
887
888
889
890
891
892
893
894

	impl_outer_origin! {
		pub enum Origin for Test {}
	}

	// For testing the module, we construct most of a mock runtime. This means
	// first constructing a configuration type (`Test`) which `impl`s each of the
	// configuration traits of modules we want to use.
	#[derive(Clone, Eq, PartialEq)]
	pub struct Test;
895
	parameter_types! {
896
		pub const BlockHashCount: u32 = 250;
897
898
899
		pub const MaximumBlockWeight: u32 = 4 * 1024 * 1024;
		pub const MaximumBlockLength: u32 = 4 * 1024 * 1024;
		pub const AvailableBlockRatio: Perbill = Perbill::from_percent(75);
900
	}
Gavin Wood's avatar
Gavin Wood committed
901
902
	impl system::Trait for Test {
		type Origin = Origin;
903
		type Call = ();
Gavin Wood's avatar
Gavin Wood committed
904
905
906
907
908
909
910
911
		type Index = u64;
		type BlockNumber = u64;
		type Hash = H256;
		type Hashing = BlakeTwo256;
		type AccountId = u64;
		type Lookup = IdentityLookup<Self::AccountId>;
		type Header = Header;
		type Event = ();
912
		type BlockHashCount = BlockHashCount;
913
914
915
		type MaximumBlockWeight = MaximumBlockWeight;
		type MaximumBlockLength = MaximumBlockLength;
		type AvailableBlockRatio = AvailableBlockRatio;
916
		type Version = ();
917
		type ModuleToIndex = ();
918
		type AccountData = balances::AccountData<u64>;
Gavin Wood's avatar
Gavin Wood committed
919
		type OnNewAccount = ();
920
		type OnKilledAccount = Balances;
Gavin Wood's avatar
Gavin Wood committed
921
922
	}

Gavin Wood's avatar
Gavin Wood committed
923
	parameter_types! {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
924
		pub const ExistentialDeposit: u64 = 1;
Gavin Wood's avatar
Gavin Wood committed
925
926
	}

Gavin Wood's avatar
Gavin Wood committed
927
928
	impl balances::Trait for Test {
		type Balance = u64;
Gavin Wood's avatar
Gavin Wood committed
929
		type Event = ();
Gavin Wood's avatar
Gavin Wood committed
930
		type DustRemoval = ();
Gavin Wood's avatar
Gavin Wood committed
931
		type ExistentialDeposit = ExistentialDeposit;
932
		type AccountStore = System;
Gavin Wood's avatar
Gavin Wood committed
933
934
935
936
937
938
939
940
	}

	thread_local! {
		pub static PARACHAIN_COUNT: RefCell<u32> = RefCell::new(0);
		pub static PARACHAINS:
			RefCell<HashMap<u32, (Vec<u8>, Vec<u8>)>> = RefCell::new(HashMap::new());
	}

941
942
943
	const MAX_CODE_SIZE: u32 = 100;
	const MAX_HEAD_DATA_SIZE: u32 = 10;

Gavin Wood's avatar
Gavin Wood committed
944
	pub struct TestParachains;
945
946
	impl Registrar<u64> for TestParachains {
		fn new_id() -> ParaId {
Gavin Wood's avatar
Gavin Wood committed
947
948
949
950
951
			PARACHAIN_COUNT.with(|p| {
				*p.borrow_mut() += 1;
				(*p.borrow() - 1).into()
			})
		}
952
953
954
955
956
957
958
959
960

		fn head_data_size_allowed(head_data_size: u32) -> bool {
			head_data_size <= MAX_HEAD_DATA_SIZE
		}

		fn code_size_allowed(code_size: u32) -> bool {
			code_size <= MAX_CODE_SIZE
		}

961
962
963
		fn register_para(
			id: ParaId,
			_info: ParaInfo,
Gavin Wood's avatar
Gavin Wood committed
964
965
			code: Vec<u8>,
			initial_head_data: Vec<u8>
966
		) -> DispatchResult {
Gavin Wood's avatar
Gavin Wood committed
967
			PARACHAINS.with(|p| {
968
				if p.borrow().contains_key(&id.into()) {
Gavin Wood's avatar
Gavin Wood committed
969
970
					panic!("ID already exists")
				}
971
				p.borrow_mut().insert(id.into(), (code, initial_head_data));
Gavin Wood's avatar
Gavin Wood committed
972
973
974
				Ok(())
			})
		}
975
		fn deregister_para(id: ParaId) -> DispatchResult {
Gavin Wood's avatar
Gavin Wood committed
976
			PARACHAINS.with(|p| {
977
				if !p.borrow().contains_key(&id.into()) {
Gavin Wood's avatar
Gavin Wood committed
978
979
					panic!("ID doesn't exist")
				}
980
				p.borrow_mut().remove(&id.into());
Gavin Wood's avatar
Gavin Wood committed
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
				Ok(())
			})
		}
	}

	fn reset_count() {
		PARACHAIN_COUNT.with(|p| *p.borrow_mut() = 0);
	}

	fn with_parachains<T>(f: impl FnOnce(&HashMap<u32, (Vec<u8>, Vec<u8>)>) -> T) -> T {
		PARACHAINS.with(|p| f(&*p.borrow()))
	}

	parameter_types!{
		pub const LeasePeriod: u64 = 10;
		pub const EndingPeriod: u64 = 3;
	}

	impl Trait for Test {
		type Event = ();
		type Currency = Balances;
		type Parachains = TestParachains;
		type LeasePeriod = LeasePeriod;
		type EndingPeriod = EndingPeriod;
1005
		type Randomness = RandomnessCollectiveFlip;
Gavin Wood's avatar
Gavin Wood committed
1006
1007
1008
1009
1010
	}

	type System = system::Module<Test>;
	type Balances = balances::Module<Test>;
	type Slots = Module<Test>;
1011
	type RandomnessCollectiveFlip = randomness_collective_flip::Module<Test>;
Gavin Wood's avatar
Gavin Wood committed
1012
1013
1014

	// This function basically just builds a genesis storage key/value store according to
	// our desired mock up.
1015
	fn new_test_ext() -> sp_io::TestExternalities {
1016
1017
		let mut t = system::GenesisConfig::default().build_storage::<Test>().unwrap();
		balances::GenesisConfig::<Test>{
Gavin Wood's avatar
Gavin Wood committed
1018
			balances: vec![(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)],
1019
		}.assimilate_storage(&mut t).unwrap();
Gavin Wood's avatar
Gavin Wood committed
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
		t.into()
	}

	fn run_to_block(n: u64) {
		while System::block_number() < n {
			Slots::on_finalize(System::block_number());
			Balances::on_finalize(System::block_number());
			System::on_finalize(System::block_number());
			System::set_block_number(System::block_number() + 1);
			System::on_initialize(System::block_number());
			Balances::on_initialize(System::block_number());
			Slots::on_initialize(System::block_number());
		}
	}

	#[test]
	fn basic_setup_works() {
1037
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
			assert_eq!(Slots::auction_counter(), 0);
			assert_eq!(Slots::deposit_held(&0u32.into()), 0);
			assert_eq!(Slots::is_in_progress(), false);
			assert_eq!(Slots::is_ending(System::block_number()), None);

			run_to_block(10);

			assert_eq!(Slots::auction_counter(), 0);
			assert_eq!(Slots::deposit_held(&0u32.into()), 0);
			assert_eq!(Slots::is_in_progress(), false);
			assert_eq!(Slots::is_ending(System::block_number()), None);
		});
	}

	#[test]
	fn can_start_auction() {
1054
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1055
1056
			run_to_block(1);

1057
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1058
1059
1060
1061
1062
1063
1064
1065
1066

			assert_eq!(Slots::auction_counter(), 1);
			assert_eq!(Slots::is_in_progress(), true);
			assert_eq!(Slots::is_ending(System::block_number()), None);
		});
	}

	#[test]
	fn auction_proceeds_correctly() {
1067
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1068
1069
			run_to_block(1);

1070
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111

			assert_eq!(Slots::auction_counter(), 1);
			assert_eq!(Slots::is_in_progress(), true);
			assert_eq!(Slots::is_ending(System::block_number()), None);

			run_to_block(2);
			assert_eq!(Slots::is_in_progress(), true);
			assert_eq!(Slots::is_ending(System::block_number()), None);

			run_to_block(3);
			assert_eq!(Slots::is_in_progress(), true);
			assert_eq!(Slots::is_ending(System::block_number()), None);

			run_to_block(4);
			assert_eq!(Slots::is_in_progress(), true);
			assert_eq!(Slots::is_ending(System::block_number()), None);

			run_to_block(5);
			assert_eq!(Slots::is_in_progress(), true);
			assert_eq!(Slots::is_ending(System::block_number()), None);

			run_to_block(6);
			assert_eq!(Slots::is_in_progress(), true);
			assert_eq!(Slots::is_ending(System::block_number()), Some(0));

			run_to_block(7);
			assert_eq!(Slots::is_in_progress(), true);
			assert_eq!(Slots::is_ending(System::block_number()), Some(1));

			run_to_block(8);
			assert_eq!(Slots::is_in_progress(), true);
			assert_eq!(Slots::is_ending(System::block_number()), Some(2));

			run_to_block(9);
			assert_eq!(Slots::is_in_progress(), false);
			assert_eq!(Slots::is_ending(System::block_number()), None);
		});
	}

	#[test]
	fn can_win_auction() {
1112
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1113
1114
			run_to_block(1);

1115
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1116
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 4, 1));
Gavin Wood's avatar
Gavin Wood committed
1117
1118
			assert_eq!(Balances::reserved_balance(1), 1);
			assert_eq!(Balances::free_balance(1), 9);
Gavin Wood's avatar
Gavin Wood committed
1119
1120
1121

			run_to_block(9);
			assert_eq!(Slots::onboard_queue(1), vec![0.into()]);
thiolliere's avatar
thiolliere committed
1122
			assert_eq!(Slots::onboarding(ParaId::from(0)),
Gavin Wood's avatar
Gavin Wood committed
1123
1124
1125
				Some((1, IncomingParachain::Unset(NewBidder { who: 1, sub: 0 })))
			);
			assert_eq!(Slots::deposit_held(&0.into()), 1);
Gavin Wood's avatar
Gavin Wood committed
1126
1127
			assert_eq!(Balances::reserved_balance(1), 0);
			assert_eq!(Balances::free_balance(1), 9);
Gavin Wood's avatar
Gavin Wood committed
1128
1129
1130
1131
1132
		});
	}

	#[test]
	fn offboarding_works() {
1133
		new_test_ext().execute_with(|| {
1134
1135
1136
			run_to_block(1);
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 4, 1));
Gavin Wood's avatar
Gavin Wood committed
1137
			assert_eq!(Balances::free_balance(1), 9);
1138
1139
1140

			run_to_block(9);
			assert_eq!(Slots::deposit_held(&0.into()), 1);
thiolliere's avatar
thiolliere committed
1141
			assert_eq!(Slots::deposits(ParaId::from(0))[0], 0);
1142
1143
1144

			run_to_block(50);
			assert_eq!(Slots::deposit_held(&0.into()), 0);
Gavin Wood's avatar
Gavin Wood committed
1145
			assert_eq!(Balances::free_balance(1), 10);
1146
1147
1148
1149
1150
		});
	}

	#[test]
	fn set_offboarding_works() {
1151
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1152
			run_to_block(1);
1153
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1154
1155
1156
1157
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 4, 1));

			run_to_block(9);
			assert_eq!(Slots::deposit_held(&0.into()), 1);
thiolliere's avatar
thiolliere committed
1158
			assert_eq!(Slots::deposits(ParaId::from(0))[0], 0);
Gavin Wood's avatar
Gavin Wood committed
1159
1160
1161
1162
1163
1164
1165

			run_to_block(49);
			assert_eq!(Slots::deposit_held(&0.into()), 1);
			assert_ok!(Slots::set_offboarding(Origin::signed(ParaId::from(0).into_account()), 10));

			run_to_block(50);
			assert_eq!(Slots::deposit_held(&0.into()), 0);
Gavin Wood's avatar
Gavin Wood committed
1166
			assert_eq!(Balances::free_balance(10), 1);
Gavin Wood's avatar
Gavin Wood committed
1167
1168
1169
1170
1171
		});
	}

	#[test]
	fn onboarding_works() {
1172
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1173
			run_to_block(1);
1174
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1175
1176
1177
1178
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 4, 1));

			run_to_block(9);
			let h = BlakeTwo256::hash(&[42u8][..]);
1179
			assert_ok!(Slots::fix_deploy_data(Origin::signed(1), 0, 0.into(), h, 1, vec![69]));
Gavin Wood's avatar
Gavin Wood committed
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
			assert_ok!(Slots::elaborate_deploy_data(Origin::signed(0), 0.into(), vec![42]));

			run_to_block(10);
			with_parachains(|p| {
				assert_eq!(p.len(), 1);
				assert_eq!(p[&0], (vec![42], vec![69]));
			});
		});
	}

	#[test]
	fn late_onboarding_works() {
1192
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1193
			run_to_block(1);
1194
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1195
1196
1197
1198
1199
1200
1201
1202
1203
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 4, 1));

			run_to_block(10);
			with_parachains(|p| {
				assert_eq!(p.len(), 0);
			});

			run_to_block(11);
			let h = BlakeTwo256::hash(&[42u8][..]);
1204
			assert_ok!(Slots::fix_deploy_data(Origin::signed(1), 0, 0.into(), h, 1, vec![69]));
Gavin Wood's avatar
Gavin Wood committed
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
			assert_ok!(Slots::elaborate_deploy_data(Origin::signed(0), 0.into(), vec![42]));
			with_parachains(|p| {
				assert_eq!(p.len(), 1);
				assert_eq!(p[&0], (vec![42], vec![69]));
			});
		});
	}

	#[test]
	fn under_bidding_works() {
1215
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1216
			run_to_block(1);
1217
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1218
1219
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 4, 5));
			assert_ok!(Slots::bid(Origin::signed(2), 0, 1, 1, 4, 1));
Gavin Wood's avatar
Gavin Wood committed
1220
1221
			assert_eq!(Balances::reserved_balance(2), 0);
			assert_eq!(Balances::free_balance(2), 20);
Gavin Wood's avatar
Gavin Wood committed
1222
1223
1224
1225
1226
1227
1228
1229
1230
			assert_eq!(
				Slots::winning(0).unwrap()[SlotRange::ZeroThree as u8 as usize],
				Some((Bidder::New(NewBidder{who: 1, sub: 0}), 5))
			);
		});
	}

	#[test]
	fn should_choose_best_combination() {
1231
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1232
			run_to_block(1);
1233
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1234
1235
1236
1237
1238
1239
1240
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 1, 1));
			assert_ok!(Slots::bid(Origin::signed(2), 0, 1, 2, 3, 1));
			assert_ok!(Slots::bid(Origin::signed(3), 0, 1, 4, 4, 2));
			assert_ok!(Slots::bid(Origin::signed(1), 1, 1, 1, 4, 1));
			run_to_block(9);
			assert_eq!(Slots::onboard_queue(1), vec![0.into()]);
			assert_eq!(
thiolliere's avatar
thiolliere committed
1241
				Slots::onboarding(ParaId::from(0)),
Gavin Wood's avatar
Gavin Wood committed
1242
1243
1244
1245
				Some((1, IncomingParachain::Unset(NewBidder { who: 1, sub: 0 })))
			);
			assert_eq!(Slots::onboard_queue(2), vec![1.into()]);
			assert_eq!(
thiolliere's avatar
thiolliere committed
1246
				Slots::onboarding(ParaId::from(1)),
Gavin Wood's avatar
Gavin Wood committed
1247
1248
1249
1250
				Some((2, IncomingParachain::Unset(NewBidder { who: 2, sub: 0 })))
			);
			assert_eq!(Slots::onboard_queue(4), vec![2.into()]);
			assert_eq!(
thiolliere's avatar
thiolliere committed
1251
				Slots::onboarding(ParaId::from(2)),
Gavin Wood's avatar
Gavin Wood committed
1252
1253
1254
1255
1256
1257
1258
				Some((4, IncomingParachain::Unset(NewBidder { who: 3, sub: 0 })))
			);
		});
	}

	#[test]
	fn independent_bids_should_fail() {
1259
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1260
			run_to_block(1);
1261
			assert_ok!(Slots::new_auction(Origin::ROOT, 1, 1));
Gavin Wood's avatar
Gavin Wood committed
1262
1263
1264
1265
1266
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 2, 1));
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 2, 4, 1));
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 2, 2, 1));
			assert_noop!(
				Slots::bid(Origin::signed(1), 0, 1, 3, 3, 1),
1267
				Error::<Test>::NonIntersectingRange
Gavin Wood's avatar
Gavin Wood committed
1268
1269
1270
1271
1272
1273
			);
		});
	}

	#[test]
	fn multiple_onboards_offboards_should_work() {
1274
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1275
			run_to_block(1);
1276
			assert_ok!(Slots::new_auction(Origin::ROOT, 1, 1));
Gavin Wood's avatar
Gavin Wood committed
1277
1278
1279
1280
1281
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 1, 1));
			assert_ok!(Slots::bid(Origin::signed(2), 0, 1, 2, 3, 1));
			assert_ok!(Slots::bid(Origin::signed(3), 0, 1, 4, 4, 1));

			run_to_block(5);
1282
			assert_ok!(Slots::new_auction(Origin::ROOT, 1, 1));
Gavin Wood's avatar
Gavin Wood committed
1283
1284
1285
1286
1287
1288
			assert_ok!(Slots::bid(Origin::signed(4), 1, 2, 1, 2, 1));
			assert_ok!(Slots::bid(Origin::signed(5), 1, 2, 3, 4, 1));

			run_to_block(9);
			assert_eq!(Slots::onboard_queue(1), vec![0.into(), 3.into()]);
			assert_eq!(
thiolliere's avatar
thiolliere committed
1289
				Slots::onboarding(ParaId::from(0)),
Gavin Wood's avatar
Gavin Wood committed
1290
1291
1292
				Some((1, IncomingParachain::Unset(NewBidder { who: 1, sub: 0 })))
			);
			assert_eq!(
thiolliere's avatar
thiolliere committed
1293
				Slots::onboarding(ParaId::from(3)),
Gavin Wood's avatar
Gavin Wood committed
1294
1295
1296
1297
				Some((1, IncomingParachain::Unset(NewBidder { who: 4, sub: 1 })))
			);
			assert_eq!(Slots::onboard_queue(2), vec![1.into()]);
			assert_eq!(
thiolliere's avatar
thiolliere committed
1298
				Slots::onboarding(ParaId::from(1)),
Gavin Wood's avatar
Gavin Wood committed
1299
1300
1301
1302
				Some((2, IncomingParachain::Unset(NewBidder { who: 2, sub: 0 })))
			);
			assert_eq!(Slots::onboard_queue(3), vec![4.into()]);
			assert_eq!(
thiolliere's avatar
thiolliere committed
1303
				Slots::onboarding(ParaId::from(4)),
Gavin Wood's avatar
Gavin Wood committed
1304
1305
1306
1307
				Some((3, IncomingParachain::Unset(NewBidder { who: 5, sub: 1 })))
			);
			assert_eq!(Slots::onboard_queue(4), vec![2.into()]);
			assert_eq!(
thiolliere's avatar
thiolliere committed
1308
				Slots::onboarding(ParaId::from(2)),
Gavin Wood's avatar
Gavin Wood committed
1309
1310
1311
1312
1313
				Some((4, IncomingParachain::Unset(NewBidder { who: 3, sub: 0 })))
			);

			for &(para, sub, acc) in &[(0, 0, 1), (1, 0, 2), (2, 0, 3), (3, 1, 4), (4, 1, 5)] {
				let h = BlakeTwo256::hash(&[acc][..]);
1314
				assert_ok!(Slots::fix_deploy_data(Origin::signed(acc as _), sub, para.into(), h, 1, vec![acc]));
Gavin Wood's avatar
Gavin Wood committed
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
				assert_ok!(Slots::elaborate_deploy_data(Origin::signed(0), para.into(), vec![acc]));
			}

			run_to_block(10);
			with_parachains(|p| {
				assert_eq!(p.len(), 2);
				assert_eq!(p[&0], (vec![1], vec![1]));
				assert_eq!(p[&3], (vec![4], vec![4]));
			});
			run_to_block(20);
			with_parachains(|p| {
				assert_eq!(p.len(), 2);
				assert_eq!(p[&1], (vec![2], vec![2]));
				assert_eq!(p[&3], (vec![4], vec![4]));
			});
			run_to_block(30);
			with_parachains(|p| {
				assert_eq!(p.len(), 2);
				assert_eq!(p[&1], (vec![2], vec![2]));
				assert_eq!(p[&4], (vec![5], vec![5]));
			});
			run_to_block(40);
			with_parachains(|p| {
				assert_eq!(p.len(), 2);
				assert_eq!(p[&2], (vec![3], vec![3]));
				assert_eq!(p[&4], (vec![5], vec![5]));
			});
			run_to_block(50);
			with_parachains(|p| {
				assert_eq!(p.len(), 0);
			});
		});
	}

	#[test]
	fn extensions_should_work() {
1351
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1352
			run_to_block(1);
1353
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1354
1355
1356
1357
1358
1359
1360
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 1, 1));

			run_to_block(9);
			assert_eq!(Slots::onboard_queue(1), vec![0.into()]);

			run_to_block(10);
			let h = BlakeTwo256::hash(&[1u8][..]);
1361
			assert_ok!(Slots::fix_deploy_data(Origin::signed(1), 0, 0.into(), h, 1, vec![1]));
Gavin Wood's avatar
Gavin Wood committed
1362
1363
			assert_ok!(Slots::elaborate_deploy_data(Origin::signed(0), 0.into(), vec![1]));

1364
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 2));
Gavin Wood's avatar
Gavin Wood committed
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
			assert_ok!(Slots::bid_renew(Origin::signed(ParaId::from(0).into_account()), 2, 2, 2, 1));

			with_parachains(|p| {
				assert_eq!(p.len(), 1);
				assert_eq!(p[&0], (vec![1], vec![1]));
			});

			run_to_block(20);
			with_parachains(|p| {
				assert_eq!(p.len(), 1);
				assert_eq!(p[&0], (vec![1], vec![1]));
			});
1377
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 2));
Gavin Wood's avatar
Gavin Wood committed
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
			assert_ok!(Balances::transfer(Origin::signed(1), ParaId::from(0).into_account(), 1));
			assert_ok!(Slots::bid_renew(Origin::signed(ParaId::from(0).into_account()), 3, 3, 3, 2));

			run_to_block(30);
			with_parachains(|p| {
				assert_eq!(p.len(), 1);
				assert_eq!(p[&0], (vec![1], vec![1]));
			});

			run_to_block(40);
			with_parachains(|p| {
				assert_eq!(p.len(), 0);
			});
		});
	}

	#[test]
	fn renewal_with_lower_value_should_work() {
1396
		new_test_ext().execute_with(|| {
Gavin Wood's avatar
Gavin Wood committed
1397
			run_to_block(1);
1398
			assert_ok!(Slots::new_auction(Origin::ROOT, 5, 1));
Gavin Wood's avatar
Gavin Wood committed
1399
1400
1401
1402
1403
1404
1405
			assert_ok!(Slots::bid(Origin::signed(1), 0, 1, 1, 1, 5));

			run_to_block(9);
			assert_eq!(Slots::onboard_queue(1), vec![0.into()]);

			run_to_block(10);
			let h = BlakeTwo256::hash(&[1u8][..]);
1406
			assert_ok!(Slots::fix_deploy_data(Origin::signed(1), 0, 0.into(), h, 1, vec![1]));
Gavin Wood's avatar
Gavin Wood committed
1407
1408
			assert_ok!(Slots::elaborate_deploy_data(Origin::signed(0), 0.into(), <