///|
pub struct MemoryRegion {
  name_value : String
  start_value : UInt64
  end_exclusive_value : UInt64
  writable_value : Bool
  executable_value : Bool
} derive(Eq, Debug)

///|
pub struct MemoryMap {
  region_values : Array[MemoryRegion]
} derive(Eq, Debug)

///|
pub struct SegmentPlacement {
  start_value : UInt64
  end_exclusive_value : UInt64
  mapped_bytes_value : UInt64
  unmapped_bytes_value : UInt64
  region_name_values : Array[String]
} derive(Eq, Debug)

///|
pub struct ImageLayout {
  placement_values : Array[SegmentPlacement]
  mapped_bytes_value : UInt64
  unmapped_bytes_value : UInt64
  fully_mapped_segments_value : Int
  partially_mapped_segments_value : Int
  unmapped_segments_value : Int
  entry_region_value : String?
  entry_was_present_value : Bool
} derive(Eq, Debug)

///|
fn layout_error(code : FirmwareErrorCode, message : String) -> FirmwareError {
  FirmwareError::new(code, message, SourcePosition::line(0))
}

///|
pub fn MemoryRegion::create(
  name : String,
  start : UInt64,
  end_exclusive : UInt64,
  writable? : Bool = false,
  executable? : Bool = false,
) -> Result[MemoryRegion, FirmwareError] {
  if name.length() == 0 {
    return Err(layout_error(IntegrityViolation, "memory region name is empty"))
  }
  if start >= end_exclusive {
    return Err(
      layout_error(
        ImageInvalidRange,
        "memory region must use a non-empty half-open address range",
      ),
    )
  }
  Ok({
    name_value: name,
    start_value: start,
    end_exclusive_value: end_exclusive,
    writable_value: writable,
    executable_value: executable,
  })
}

///|
pub fn MemoryRegion::name(self : MemoryRegion) -> String {
  self.name_value
}

///|
pub fn MemoryRegion::start(self : MemoryRegion) -> UInt64 {
  self.start_value
}

///|
pub fn MemoryRegion::end_exclusive(self : MemoryRegion) -> UInt64 {
  self.end_exclusive_value
}

///|
pub fn MemoryRegion::length(self : MemoryRegion) -> UInt64 {
  self.end_exclusive_value - self.start_value
}

///|
pub fn MemoryRegion::writable(self : MemoryRegion) -> Bool {
  self.writable_value
}

///|
pub fn MemoryRegion::executable(self : MemoryRegion) -> Bool {
  self.executable_value
}

///|
pub fn MemoryRegion::contains_address(
  self : MemoryRegion,
  address : UInt64,
) -> Bool {
  address >= self.start_value && address < self.end_exclusive_value
}

///|
pub fn MemoryRegion::contains_range(
  self : MemoryRegion,
  start : UInt64,
  end_exclusive : UInt64,
) -> Bool {
  start < end_exclusive &&
  start >= self.start_value &&
  end_exclusive <= self.end_exclusive_value
}

///|
fn region_insert_index(regions : Array[MemoryRegion], start : UInt64) -> Int {
  let mut index = 0
  while index < regions.length() && regions[index].start() < start {
    index = index + 1
  }
  index
}

///|
pub fn MemoryMap::create(
  regions : Array[MemoryRegion],
) -> Result[MemoryMap, FirmwareError] {
  let ordered : Array[MemoryRegion] = []
  for region in regions {
    for existing in ordered {
      if existing.name() == region.name() {
        return Err(
          layout_error(
            IntegrityViolation,
            "memory map contains duplicate region names",
          ),
        )
      }
    }
    let index = region_insert_index(ordered, region.start())
    if index > 0 && ordered[index - 1].end_exclusive() > region.start() {
      return Err(layout_error(ImageOverlap, "memory map regions overlap"))
    }
    if index < ordered.length() &&
      region.end_exclusive() > ordered[index].start() {
      return Err(layout_error(ImageOverlap, "memory map regions overlap"))
    }
    ordered.insert(index, region)
  }
  Ok({ region_values: ordered })
}

///|
pub fn MemoryMap::regions(self : MemoryMap) -> Array[MemoryRegion] {
  self.region_values.copy()
}

///|
pub fn MemoryMap::region_count(self : MemoryMap) -> Int {
  self.region_values.length()
}

///|
pub fn MemoryMap::total_capacity(self : MemoryMap) -> UInt64 {
  let mut total = 0UL
  for region in self.region_values {
    total = total + region.length()
  }
  total
}

///|
pub fn MemoryMap::writable_capacity(self : MemoryMap) -> UInt64 {
  let mut total = 0UL
  for region in self.region_values {
    if region.writable() {
      total = total + region.length()
    }
  }
  total
}

///|
pub fn MemoryMap::executable_capacity(self : MemoryMap) -> UInt64 {
  let mut total = 0UL
  for region in self.region_values {
    if region.executable() {
      total = total + region.length()
    }
  }
  total
}

///|
/// Find one region that completely contains a non-empty half-open range.
pub fn MemoryMap::region_containing_range(
  self : MemoryMap,
  start : UInt64,
  end_exclusive : UInt64,
) -> MemoryRegion? {
  if start >= end_exclusive {
    return None
  }
  for region in self.region_values {
    if region.contains_range(start, end_exclusive) {
      return Some(region)
    }
    if region.start() > start {
      return None
    }
  }
  None
}

///|
pub fn MemoryMap::region_at(
  self : MemoryMap,
  address : UInt64,
) -> MemoryRegion? {
  for region in self.region_values {
    if region.contains_address(address) {
      return Some(region)
    }
    if region.start() > address {
      return None
    }
  }
  None
}

///|
fn greater_address(left : UInt64, right : UInt64) -> UInt64 {
  if left > right {
    left
  } else {
    right
  }
}

///|
fn lesser_address(left : UInt64, right : UInt64) -> UInt64 {
  if left < right {
    left
  } else {
    right
  }
}

///|
fn place_segment(segment : ImageSegment, map : MemoryMap) -> SegmentPlacement {
  let names : Array[String] = []
  let mut mapped = 0UL
  for region in map.region_values {
    let start = greater_address(segment.address(), region.start())
    let end = lesser_address(segment.end_exclusive(), region.end_exclusive())
    if start < end {
      mapped = mapped + (end - start)
      names.push(region.name())
    }
  }
  let length = segment.length().to_uint64()
  {
    start_value: segment.address(),
    end_exclusive_value: segment.end_exclusive(),
    mapped_bytes_value: mapped,
    unmapped_bytes_value: length - mapped,
    region_name_values: names,
  }
}

///|
/// Compare each sparse image segment with a validated non-overlapping map.
pub fn analyze_image_layout(
  image : FirmwareImage,
  map : MemoryMap,
) -> ImageLayout {
  let placements : Array[SegmentPlacement] = []
  let mut mapped = 0UL
  let mut unmapped = 0UL
  let mut fully_mapped = 0
  let mut partially_mapped = 0
  let mut fully_unmapped = 0
  for segment in image.segments() {
    let placement = place_segment(segment, map)
    mapped = mapped + placement.mapped_bytes()
    unmapped = unmapped + placement.unmapped_bytes()
    if placement.mapped_bytes() == 0UL {
      fully_unmapped = fully_unmapped + 1
    } else if placement.unmapped_bytes() == 0UL {
      fully_mapped = fully_mapped + 1
    } else {
      partially_mapped = partially_mapped + 1
    }
    placements.push(placement)
  }
  let entry_region = match image.entry_point() {
    Some(address) =>
      match map.region_at(address) {
        Some(region) => Some(region.name())
        None => None
      }
    None => None
  }
  {
    placement_values: placements,
    mapped_bytes_value: mapped,
    unmapped_bytes_value: unmapped,
    fully_mapped_segments_value: fully_mapped,
    partially_mapped_segments_value: partially_mapped,
    unmapped_segments_value: fully_unmapped,
    entry_region_value: entry_region,
    entry_was_present_value: image.entry_point() is Some(_),
  }
}

///|
pub fn SegmentPlacement::start(self : SegmentPlacement) -> UInt64 {
  self.start_value
}

///|
pub fn SegmentPlacement::end_exclusive(self : SegmentPlacement) -> UInt64 {
  self.end_exclusive_value
}

///|
pub fn SegmentPlacement::mapped_bytes(self : SegmentPlacement) -> UInt64 {
  self.mapped_bytes_value
}

///|
pub fn SegmentPlacement::unmapped_bytes(self : SegmentPlacement) -> UInt64 {
  self.unmapped_bytes_value
}

///|
pub fn SegmentPlacement::region_names(self : SegmentPlacement) -> Array[String] {
  self.region_name_values.copy()
}

///|
pub fn ImageLayout::placements(self : ImageLayout) -> Array[SegmentPlacement] {
  self.placement_values.copy()
}

///|
pub fn ImageLayout::segment_count(self : ImageLayout) -> Int {
  self.placement_values.length()
}

///|
pub fn ImageLayout::mapped_bytes(self : ImageLayout) -> UInt64 {
  self.mapped_bytes_value
}

///|
pub fn ImageLayout::unmapped_bytes(self : ImageLayout) -> UInt64 {
  self.unmapped_bytes_value
}

///|
pub fn ImageLayout::fully_mapped_segments(self : ImageLayout) -> Int {
  self.fully_mapped_segments_value
}

///|
pub fn ImageLayout::partially_mapped_segments(self : ImageLayout) -> Int {
  self.partially_mapped_segments_value
}

///|
pub fn ImageLayout::unmapped_segments(self : ImageLayout) -> Int {
  self.unmapped_segments_value
}

///|
pub fn ImageLayout::entry_region(self : ImageLayout) -> String? {
  self.entry_region_value
}

///|
pub fn ImageLayout::accepted(self : ImageLayout) -> Bool {
  self.unmapped_bytes_value == 0UL &&
  (!self.entry_was_present_value || self.entry_region_value is Some(_))
}