odem-rs 0.3.0

//! This module implements a medium-sized simulation model of an elevator
//! system, originally described in *The Art of Computer Programming, Volume 1*
//! by Donald Knuth (Section 2.2.5). The simulation is inspired by the
//! historical elevator system in the Mathematics building at Caltech.
//!
//! The simulation demonstrates the use of asynchronous agents to model both the
//! elevator and passengers. It showcases coordination and synchronization of
//! events using control variables and chain-based queues, as well as handling
//! of special cases like door operation, passenger patience, and directional
//! floor calls.
//! It intentionally doesn't follow the implementation in the book but uses the
//! native concepts of odem-rs directly in the hopes of improving readability
//! and conciseness.
//!
//! ## Components
//!
//! - `Caltech`: Global configuration and state for the simulation.
//! - `Passenger`: An agent representing an individual calling the elevator,
//!   waiting, boarding, and eventually disembarking.
//! - `Elevator`: An agent controlling elevator movement, door operations, and
//!   servicing floor requests.
//!
//! ## Simulation Flow
//!
//! 1. Passengers are generated randomly and attempt to board the elevator.
//! 2. Each passenger presses the appropriate call button (upward or downward)
//!    based on their desired direction.
//! 3. The elevator monitors these calls and moves accordingly, opening its
//!    doors to allow passengers to board or exit.
//! 4. Synchronization mechanisms (using chains and control flags) ensure that
//!    door operations and boarding are handled without race conditions.
//!
//! This implementation uses the odem-rs simulation framework and serves as an
//! educational example of applying fundamental data structures in simulation
//! models.

use core::{cell::Cell, pin::pin};
use odem_rs::{
	prelude::*,
	sync::{Subscriber, chain::Chain},
};
use rand_distr::Exp;
use tracing::{Level, debug, info};

/// Global configuration for the elevator simulation.
#[derive(Config, Default)]
#[time(Time<f64>)]
#[rank(u32 = 0)]
struct Caltech {
	/// A stream of independent PRNGs.
	rng_stream: RngStream,

	/// The current position of the elevator.
	floor: Cell<usize>,
	/// A variable which is `false` except during the time people are getting
	/// in or out of the elevator.
	d1: Control<bool>,

	/// The elevator cabin, represented as a [`Chain`] of [`Passenger`].
	///
	/// Passengers queue up here and are reactivated by the elevator once it
	/// reaches their floor and the door is open. Reactivation is in stack
	/// order.
	cabin: Chain,
	/// Buttons for every floor pressed by passengers that intend to move up.
	callup: [Control<bool>; 5],
	/// Buttons for every floor pressed by passengers intending to move down.
	calldown: [Control<bool>; 5],
	/// Buttons located inside the elevator to signal where it should stop.
	callcar: [Control<bool>; 5],
}

impl Caltech {
	/// Function that determines whether a call for one of the lower floors
	/// has to be served or not.
	fn is_going_down(&self) -> bool {
		for j in 0..self.floor.get() {
			if self.callup[j].get() || self.calldown[j].get() || self.callcar[j].get() {
				return true;
			}
		}

		false
	}

	/// Function that determines whether a call for one of the upper floors
	/// has to be served or not.
	fn is_going_up(&self) -> bool {
		for j in self.floor.get() + 1..5 {
			if self.callup[j].get() || self.calldown[j].get() || self.callcar[j].get() {
				return true;
			}
		}

		false
	}

	/// Moves the elevator down one floor.
	async fn move_down(&self, sim: &Sim<Self>) {
		info!("Elevator moving down.");
		self.floor.set(self.floor.get() - 1);
		sim.advance(second::new(6.1)).await;
	}

	/// Moves the elevator up one floor.
	async fn move_up(&self, sim: &Sim<Self>) {
		info!("Elevator moving up.");
		self.floor.set(self.floor.get() + 1);
		sim.advance(second::new(5.1)).await;
	}
}

/// Main simulation routine.
///
/// Sets up the simulation by creating passenger arrivals and the elevator
/// agent, then running the simulation for a specified duration.
///
/// - Passengers are generated at random intervals (exponential distribution
///   with a rate of one every two minutes).
/// - Each passenger is assigned random origin/destination floors and a random
///   patience time.
/// - The elevator agent continuously services calls based on the state of the
///   call buttons.
#[odem_rs::main]
#[allow(dead_code)]
async fn sim_main(sim: &Sim<Caltech>, duration: Time<f64>) {
	let passengers = pin!(Pool::fixed::<10>());

	// M1. [Enter, prepare for successor]
	// Generate passengers at random intervals.
	let arrivals = pin!(Job::new(async {
		let intertime = Exp::new(0.5).unwrap();
		let rng = &mut sim.global().rng_stream.rng();

		loop {
			sim.advance(minute::new(rng.sample(intertime))).await;

			sim.activate(passengers.alloc({
				let in_floor = rng.random_range(0..5);
				let out_floor = rng.random_range(0..4);
				let out_floor = out_floor + (out_floor >= in_floor) as usize;
				let giveuptime = second::new(rng.random_range(15.0..30.0));

				Agent::build()
					.with_subject(Passenger {
						in_floor,
						out_floor,
						giveuptime,
					})
					.with_actions(Passenger::actions)
					.with_name("Man")
					.with_rank(1)
					.finish()
			}));
		}
	}));

	// Create the elevator.
	let elevator = pin!(Agent::new(Elevator));

	// Activate both passenger arrivals and the elevator.
	sim.activate(arrivals);
	sim.activate(elevator);

	// Run the simulation for the specified duration.
	sim.advance(duration).await
}

#[odem_rs::main]
#[allow(dead_code)]
async fn knuth_sim(sim: &Sim<Caltech>) {
	let passengers = pin!(Pool::fixed::<11>());

	// Generate the passengers from Knuth's trace to validate the model.
	let arrivals = [
		(
			second::new(0.0),
			Passenger {
				in_floor: 0,
				out_floor: 2,
				giveuptime: second::new(15.2),
			},
		),
		(
			second::new(3.8),
			Passenger {
				in_floor: 4,
				out_floor: 1,
				giveuptime: second::new(f64::INFINITY),
			},
		),
		(
			second::new(13.6),
			Passenger {
				in_floor: 2,
				out_floor: 1,
				giveuptime: second::new(f64::INFINITY),
			},
		),
		(
			second::new(14.1),
			Passenger {
				in_floor: 2,
				out_floor: 1,
				giveuptime: second::new(f64::INFINITY),
			},
		),
		(
			second::new(29.1),
			Passenger {
				in_floor: 3,
				out_floor: 1,
				giveuptime: second::new(f64::INFINITY),
			},
		),
		(
			second::new(36.4),
			Passenger {
				in_floor: 2,
				out_floor: 1,
				giveuptime: second::new(17.6),
			},
		),
		(
			second::new(60.2),
			Passenger {
				in_floor: 1,
				out_floor: 2,
				giveuptime: second::new(f64::INFINITY),
			},
		),
		(
			second::new(82.7),
			Passenger {
				in_floor: 1,
				out_floor: 0,
				giveuptime: second::new(f64::INFINITY),
			},
		),
		(
			second::new(87.6),
			Passenger {
				in_floor: 1,
				out_floor: 3,
				giveuptime: second::new(f64::INFINITY),
			},
		),
		(
			second::new(104.8),
			Passenger {
				in_floor: 0,
				out_floor: 4,
				giveuptime: second::new(f64::INFINITY),
			},
		),
		(
			second::new(438.4),
			Passenger {
				in_floor: 2,
				out_floor: 3,
				giveuptime: second::new(f64::INFINITY),
			},
		),
	];

	for (time, passenger) in arrivals {
		sim.schedule(
			passengers.alloc(
				Agent::build()
					.with_subject(passenger)
					.with_actions(Passenger::actions)
					.with_name("Man")
					.with_rank(1)
					.finish(),
			),
			time,
		);
	}

	// Create the elevator.
	let elevator = pin!(Agent::new(Elevator));

	// Activate the elevator.
	sim.schedule(elevator, second::new(2.0));

	// Run the simulation.
	sim.advance(second::new(1000.0)).await
}

/// Represents a passenger in the simulation.
///
/// Each passenger has an origin (`in_floor`), a destination (`out_floor`), and
/// a maximum waiting time (`giveuptime`) before giving up. The behavior models
/// the following steps:
/// 1. Pressing the appropriate call button (up or down) based on a travel
///    direction.
/// 2. Waiting in a FIFO queue for the elevator or giving up after a timeout.
/// 3. Boarding the elevator when allowed, pressing the internal destination
///    button, and waiting until the elevator reaches the destination.
/// 4. Disembarking from the elevator in an orderly, synchronized fashion.
struct Passenger {
	in_floor: usize,
	out_floor: usize,
	giveuptime: Time<f64>,
}

impl Behavior<Caltech> for Passenger {
	type Output = ();

	async fn actions(&self, sim: &Sim<Caltech>) {
		// (M1. [Enter, prepare for successor] handled in `sim_main`)
		let g = sim.global();
		let id = sim.active().label().pid.unwrap();

		debug!(
			"Man no. {id} arrives at floor {}, destination is {}.",
			self.in_floor, self.out_floor
		);

		// M2. [Signal and wait]
		// Determine the proper call button and queue based on the travel direction.
		let call_button = if self.in_floor > self.out_floor {
			&g.calldown[self.in_floor]
		} else {
			&g.callup[self.in_floor]
		};
		call_button.set(true);

		// Wait for the elevator to signal boarding or give up after a timeout.
		// The FIFO branch preempts the timeout if the elevator arrives.
		if sim
			.fork(async {
				// M3. [Enter queue]
				// Wait for the elevator to turn off the call-button.
				// (the control variable is backed by a FIFO queue and will
				//  reactivate passengers in order of their arrival)
				until!(!call_button).await;
				false
			})
			.or(async {
				// M4. [Give up]
				// (Loop due to the possibility that the elevator is there for
				//  passengers heading in a different direction; Knuth initially
				//  made the error of waiting it out, but fixed it in his code)
				loop {
					// Wait until the passenger's patience runs out.
					sim.advance(self.giveuptime).await;

					// If the elevator isn't here or busy, give up.
					if g.floor.get() != self.in_floor || !g.d1.get() {
						break true;
					}
				}
			})
			.await
		{
			debug!("Man no. {id} decides to give up and leaves.");
			return;
		}

		// M5. [Get in]
		// Board the elevator.
		until!(!g.d1).await;
		g.d1.set(true);
		debug!("Man no. {id} gets in.");
		sim.advance(second::new(2.5)).await;
		g.d1.set(false);

		// Press the internal button for the destination floor.
		g.callcar[self.out_floor].set(true);

		// Wait until the elevator reaches the destination floor.
		while g.floor.get() != self.out_floor {
			g.cabin.lifo().await;
		}

		// M6. [Get out]
		// Exit the elevator.
		until!(!g.d1).await;
		g.d1.set(true);
		debug!("Man no. {id} gets out, leaves system.");
		sim.advance(second::new(2.5)).await;
		g.d1.set(false);
	}
}

/// Represents the elevator in the simulation.
///
/// The elevator monitors floor call buttons (both external and internal) and
/// moves accordingly. Its behavior includes:
/// 1. Starting at an initial floor (floor 2).
/// 2. Opening and closing doors, including a "fluttering" mechanism where doors
///    may briefly reopen if interrupted by new requests.
/// 3. Moving floor-by-floor while checking for intermediate stops if new calls
///    are detected.
struct Elevator;

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
enum ElevatorState {
	Neutral,
	GoingUp,
	GoingDown,
}

impl Behavior<Caltech> for Elevator {
	type Output = ();

	async fn actions(&self, sim: &Sim<Caltech>) {
		let g = sim.global();

		// Start at floor 2.
		g.floor.set(2);

		let state = Cell::new(ElevatorState::Neutral);
		let door_open = Cell::new(false);

		// E5. [Close door]
		// This task is executed concurrently to the main loop on request.
		let close_door = Control::new(false);
		let e5 = pin!(Job::new(async {
			loop {
				// Wait until the job is started.
				until!(close_door).await;

				// Wait for 7.6 seconds if nobody is there, and for 2.5 seconds
				// after someone entered, whichever is shorter.
				sim.fork(sim.advance(second::new(7.6)))
					.or(async {
						// Special case only on neutral state.
						if state.get() != ElevatorState::Neutral {
							sleep().await;
						}

						until!(g.d1).await;
						sim.advance(second::new(2.5)).await;
					})
					.await;

				// Entering while the door is closing will reopen it.
				while sim
					.fork(async {
						// Doors flutter if someone is entering or exiting.
						until!(g.d1).await;
						true
					})
					.or(async {
						// Close the door.
						info!("Elevator door starts to close.");
						sim.advance(second::new(2.0)).await;
						door_open.set(false);
						close_door.set(false);
						false
					})
					.await
				{
					info!("Doors flutter.");
					sim.advance(second::new(4.0)).await;
				}
			}
		}));

		// E9. [Set inaction indicator]
		let check_inaction = Control::new(false);
		let e9 = pin!(Job::new(async {
			loop {
				// Wait for a signal from the main job.
				until!(check_inaction).await;

				if sim
					.fork(async {
						// Wait for 30 seconds.
						sim.advance(second::new(30.0)).await;
						true
					})
					.or(async {
						// Interrupting this operation restarts it.
						until!(!check_inaction).await;
						false
					})
					.await
				{
					check_inaction.set(false);

					// Remain dormant if idle at floor 2.
					if g.floor.get() == 2 {
						info!("Elevator dormant.");
						continue;
					}

					// Move to the home floor otherwise.
					g.callcar[2].set(true);
				}
			}
		}));

		sim.activate(e5);
		sim.activate(e9);

		// Helper function that checks the buttons for a floor.
		let check = async |floor: usize| {
			until!(g.callup[floor] || g.calldown[floor] || g.callcar[floor]).await;
		};

		loop {
			// E2. [Change of state]
			match state.get() {
				ElevatorState::Neutral => {}
				ElevatorState::GoingUp => {
					if g.callup[g.floor.get()].get() {
						g.callup[g.floor.get()].set(false);
					}

					if !g.is_going_up() {
						state.set(ElevatorState::Neutral);
					}
				}
				ElevatorState::GoingDown => {
					if g.calldown[g.floor.get()].get() {
						g.calldown[g.floor.get()].set(false);
					}

					if !g.is_going_down() {
						state.set(ElevatorState::Neutral);
					}
				}
			}

			// E1. [Wait for call]
			sim.fork(check(0))
				.or(check(1))
				.or(check(2))
				.or(check(3))
				.or(check(4))
				.await;

			// E2. [Change of state] (part 2)
			if state.get() == ElevatorState::Neutral {
				// DECISION subroutine
				state.set(
					// Has anyone pushed the button in the current floor?
					if g.callup[g.floor.get()].get() || g.calldown[g.floor.get()].get() {
						// Is the door open?
						if !door_open.get() {
							// Schedule its closing and open it.
							close_door.set(true);

							info!("Elevator door starts to open.");
							sim.advance(second::new(2.0)).await;
							door_open.set(true);
						}

						// Prefer the down-button over the up-button.
						if g.calldown[g.floor.get()].get() {
							g.calldown[g.floor.get()].set(false);
						} else {
							g.callup[g.floor.get()].set(false);
						}

						continue;
					} else if g.is_going_down() {
						ElevatorState::GoingDown
					} else {
						ElevatorState::GoingUp
					},
				);
			}

			// E5. [Close door]
			// If the door is open, handle closing with potential interruption.
			if door_open.get() {
				until!(!close_door).await;
			}

			// E6. [Prepare to move]
			check_inaction.set(false);

			// Move the elevator floor-by-floor toward the target.
			match state.get() {
				ElevatorState::Neutral => unreachable!(),
				ElevatorState::GoingUp => {
					// E7. [Travel up]
					sim.advance(second::new(1.5)).await;

					while g.is_going_up() {
						g.move_up(sim).await;
						if g.callcar[g.floor.get()].get() || g.callup[g.floor.get()].get() {
							break;
						}
					}

					sim.advance(second::new(1.4)).await;

					if !g.is_going_up() {
						state.set(ElevatorState::Neutral);
					}
				}
				ElevatorState::GoingDown => {
					// E8. [Travel down]
					sim.advance(second::new(1.5)).await;

					while g.is_going_down() {
						g.move_down(sim).await;
						if g.callcar[g.floor.get()].get() || g.calldown[g.floor.get()].get() {
							break;
						}
					}

					sim.advance(second::new(2.3)).await;

					if !g.is_going_down() {
						state.set(ElevatorState::Neutral);
					}
				}
			}

			// Stop the elevator and clear the button inside the cabin.
			info!("Elevator stops in floor {}.", g.floor.get());
			g.callcar[g.floor.get()].set(false);

			// E3. [Open the door]
			// Schedule the closing and open the door.
			close_door.set(true);
			check_inaction.set(true);
			info!("Elevator door starts to open.");
			sim.advance(second::new(2.0)).await;
			door_open.set(true);

			// Notify the passengers.
			g.cabin.notify();
		}
	}
}

fn main() {
	tracing_subscriber::fmt()
		.with_max_level(Level::DEBUG)
		.with_target(false)
		.with_timer(model_time!("[{time:5.1}]"))
		.compact()
		.init();

	knuth_sim();
	// sim_main(minute::new(20.0));
}