/**
 * Small teaching model of a read-only, blocking cache.
 * Address lookups model tags, set indexing and replacement only.
 * Not a cycle-accurate hardware model or a CPU performance predictor.
 */
export class Cache {
  constructor({ sizeBytes = 128, lineBytes = 16, ways = 1, policy = 'LRU' } = {}) {
    for (const [name, value] of Object.entries({ sizeBytes, lineBytes, ways })) {
      if (!Number.isSafeInteger(value) || value < 1 || value > 2 ** 20 || !Number.isInteger(Math.log2(value))) {
        throw new RangeError(`${name} must be a positive power of two no larger than 1 MiB`);
      }
    }
    if (sizeBytes < lineBytes * ways) {
      throw new RangeError('cache must have room for at least one complete set');
    }
    if (!['LRU', 'FIFO'].includes(policy)) {
      throw new RangeError('policy must be LRU or FIFO');
    }
    this.sizeBytes = sizeBytes;
    this.lineBytes = lineBytes;
    this.ways = ways;
    this.setCount = sizeBytes / (lineBytes * ways);
    this.policy = policy;
    this.sets = Array.from({ length: this.setCount }, () => []);
    this.clock = 0;
    this.hits = 0;
    this.misses = 0;
    this.evictions = 0;
  }

  access(address) {
    if (!Number.isSafeInteger(address) || address < 0 || address > 0xffffffff) {
      throw new RangeError('address must be a 32-bit unsigned integer');
    }
    const block = Math.floor(address / this.lineBytes);
    const setIndex = block % this.setCount;
    const tag = Math.floor(block / this.setCount);
    const offset = address % this.lineBytes;
    const set = this.sets[setIndex];
    const timestamp = ++this.clock;
    const present = set.find(line => line.tag === tag);
    if (present) {
      this.hits++;
      present.lastUsed = timestamp;
      return { address, setIndex, tag, offset, hit: true, evictedTag: null };
    }
    this.misses++;
    let evictedTag = null;
    if (set.length === this.ways) {
      const key = this.policy === 'LRU' ? 'lastUsed' : 'inserted';
      let oldest = 0;
      for (let i = 1; i < set.length; i++) {
        if (set[i][key] < set[oldest][key]) oldest = i;
      }
      evictedTag = set[oldest].tag;
      set.splice(oldest, 1);
      this.evictions++;
    }
    set.push({ tag, inserted: timestamp, lastUsed: timestamp });
    return { address, setIndex, tag, offset, hit: false, evictedTag };
  }

  stats() {
    const accesses = this.hits + this.misses;
    return {
      accesses,
      hits: this.hits,
      misses: this.misses,
      evictions: this.evictions,
      hitRate: accesses ? this.hits / accesses : 0,
    };
  }
}

export function simulate(addresses, configuration = {}) {
  const cache = new Cache(configuration);
  const events = Array.from(addresses, address => cache.access(address));
  return { configuration: { sizeBytes: cache.sizeBytes, lineBytes: cache.lineBytes, ways: cache.ways, policy: cache.policy, sets: cache.setCount }, ...cache.stats(), events };
}

/** One hexadecimal (0x...) or decimal byte address per line. '#' starts a comment. */
export function parseTrace(source) {
  if (typeof source !== 'string') throw new TypeError('trace must be text');
  const result = [];
  for (const [index, original] of source.split(/\r?\n/).entries()) {
    const value = original.split('#')[0].trim();
    if (!value) continue;
    if (!/^(?:0x[0-9a-f]+|[0-9]+)$/i.test(value)) {
      throw new SyntaxError(`invalid address on line ${index + 1}: ${value}`);
    }
    const address = Number(value);
    if (!Number.isSafeInteger(address) || address > 0xffffffff) {
      throw new RangeError(`address out of range on line ${index + 1}`);
    }
    result.push(address);
  }
  return result;
}