import { is } from './is.js'
import { Token, Type } from './token.js'
import { Bl, U8Bl } from './bl.js'
import { encodeErrPrefix } from './common.js'
import { quickEncodeToken } from './jump.js'
import { asU8A, compare, fromString } from './byte-utils.js'

import { encodeUint, encodeUintValue } from './0uint.js'
import { encodeNegint } from './1negint.js'
import { encodeBytes } from './2bytes.js'
import { encodeString } from './3string.js'
import { encodeArray } from './4array.js'
import { encodeMap } from './5map.js'
import { encodeTag } from './6tag.js'
import { encodeFloat, MINOR_FALSE, MINOR_TRUE, MINOR_NULL, MINOR_UNDEFINED } from './7float.js'

/**
 * @typedef {import('../interface.js').EncodeOptions} EncodeOptions
 * @typedef {import('../interface.js').OptionalTypeEncoder} OptionalTypeEncoder
 * @typedef {import('../interface.js').Reference} Reference
 * @typedef {import('../interface.js').StrictTypeEncoder} StrictTypeEncoder
 * @typedef {import('../interface.js').TokenTypeEncoder} TokenTypeEncoder
 * @typedef {import('../interface.js').TokenOrNestedTokens} TokenOrNestedTokens
 * @typedef {import('../interface.js').ByteWriter} ByteWriter
 */

/** @type {EncodeOptions} */
const defaultEncodeOptions = {
  float64: false,
  mapSorter,
  quickEncodeToken
}

/** @type {EncodeOptions} */
export const rfc8949EncodeOptions = Object.freeze({
  float64: true,
  mapSorter: rfc8949MapSorter,
  quickEncodeToken
})

/** @returns {TokenTypeEncoder[]} */
export function makeCborEncoders () {
  const encoders = []
  encoders[Type.uint.major] = encodeUint
  encoders[Type.negint.major] = encodeNegint
  encoders[Type.bytes.major] = encodeBytes
  encoders[Type.string.major] = encodeString
  encoders[Type.array.major] = encodeArray
  encoders[Type.map.major] = encodeMap
  encoders[Type.tag.major] = encodeTag
  encoders[Type.float.major] = encodeFloat
  return encoders
}

const cborEncoders = makeCborEncoders()

const defaultWriter = new Bl()

/** @implements {Reference} */
class Ref {
  /**
   * @param {object|any[]} obj
   * @param {Reference|undefined} parent
   */
  constructor (obj, parent) {
    this.obj = obj
    this.parent = parent
  }

  /**
   * @param {object|any[]} obj
   * @returns {boolean}
   */
  includes (obj) {
    /** @type {Reference|undefined} */
    let p = this
    do {
      if (p.obj === obj) {
        return true
      }
    } while (p = p.parent) // eslint-disable-line
    return false
  }

  /**
   * @param {Reference|undefined} stack
   * @param {object|any[]} obj
   * @returns {Reference}
   */
  static createCheck (stack, obj) {
    if (stack && stack.includes(obj)) {
      throw new Error(`${encodeErrPrefix} object contains circular references`)
    }
    return new Ref(obj, stack)
  }
}

const simpleTokens = {
  null: new Token(Type.null, null),
  undefined: new Token(Type.undefined, undefined),
  true: new Token(Type.true, true),
  false: new Token(Type.false, false),
  emptyArray: new Token(Type.array, 0),
  emptyMap: new Token(Type.map, 0)
}

/** @type {{[typeName: string]: StrictTypeEncoder}} */
const typeEncoders = {
  /**
   * @param {any} obj
   * @param {string} _typ
   * @param {EncodeOptions} _options
   * @param {Reference} [_refStack]
   * @returns {TokenOrNestedTokens}
   */
  number (obj, _typ, _options, _refStack) {
    if (!Number.isInteger(obj) || !Number.isSafeInteger(obj)) {
      return new Token(Type.float, obj)
    } else if (obj >= 0) {
      return new Token(Type.uint, obj)
    } else {
      return new Token(Type.negint, obj)
    }
  },

  /**
   * @param {any} obj
   * @param {string} _typ
   * @param {EncodeOptions} _options
   * @param {Reference} [_refStack]
   * @returns {TokenOrNestedTokens}
   */
  bigint (obj, _typ, _options, _refStack) {
    if (obj >= BigInt(0)) {
      return new Token(Type.uint, obj)
    } else {
      return new Token(Type.negint, obj)
    }
  },

  /**
   * @param {any} obj
   * @param {string} _typ
   * @param {EncodeOptions} _options
   * @param {Reference} [_refStack]
   * @returns {TokenOrNestedTokens}
   */
  Uint8Array (obj, _typ, _options, _refStack) {
    return new Token(Type.bytes, obj)
  },

  /**
   * @param {any} obj
   * @param {string} _typ
   * @param {EncodeOptions} _options
   * @param {Reference} [_refStack]
   * @returns {TokenOrNestedTokens}
   */
  string (obj, _typ, _options, _refStack) {
    return new Token(Type.string, obj)
  },

  /**
   * @param {any} obj
   * @param {string} _typ
   * @param {EncodeOptions} _options
   * @param {Reference} [_refStack]
   * @returns {TokenOrNestedTokens}
   */
  boolean (obj, _typ, _options, _refStack) {
    return obj ? simpleTokens.true : simpleTokens.false
  },

  /**
   * @param {any} _obj
   * @param {string} _typ
   * @param {EncodeOptions} _options
   * @param {Reference} [_refStack]
   * @returns {TokenOrNestedTokens}
   */
  null (_obj, _typ, _options, _refStack) {
    return simpleTokens.null
  },

  /**
   * @param {any} _obj
   * @param {string} _typ
   * @param {EncodeOptions} _options
   * @param {Reference} [_refStack]
   * @returns {TokenOrNestedTokens}
   */
  undefined (_obj, _typ, _options, _refStack) {
    return simpleTokens.undefined
  },

  /**
   * @param {any} obj
   * @param {string} _typ
   * @param {EncodeOptions} _options
   * @param {Reference} [_refStack]
   * @returns {TokenOrNestedTokens}
   */
  ArrayBuffer (obj, _typ, _options, _refStack) {
    return new Token(Type.bytes, new Uint8Array(obj))
  },

  /**
   * @param {any} obj
   * @param {string} _typ
   * @param {EncodeOptions} _options
   * @param {Reference} [_refStack]
   * @returns {TokenOrNestedTokens}
   */
  DataView (obj, _typ, _options, _refStack) {
    return new Token(Type.bytes, new Uint8Array(obj.buffer, obj.byteOffset, obj.byteLength))
  },

  /**
   * @param {any} obj
   * @param {string} _typ
   * @param {EncodeOptions} options
   * @param {Reference} [refStack]
   * @returns {TokenOrNestedTokens}
   */
  Array (obj, _typ, options, refStack) {
    if (!obj.length) {
      if (options.addBreakTokens === true) {
        return [simpleTokens.emptyArray, new Token(Type.break)]
      }
      return simpleTokens.emptyArray
    }
    refStack = Ref.createCheck(refStack, obj)
    const entries = []
    let i = 0
    for (const e of obj) {
      entries[i++] = objectToTokens(e, options, refStack)
    }
    if (options.addBreakTokens) {
      return [new Token(Type.array, obj.length), entries, new Token(Type.break)]
    }
    return [new Token(Type.array, obj.length), entries]
  },

  /**
   * @param {any} obj
   * @param {string} typ
   * @param {EncodeOptions} options
   * @param {Reference} [refStack]
   * @returns {TokenOrNestedTokens}
   */
  Object (obj, typ, options, refStack) {
    // could be an Object or a Map
    const isMap = typ !== 'Object'
    // it's slightly quicker to use Object.keys() than Object.entries()
    const keys = isMap ? obj.keys() : Object.keys(obj)
    const maxLength = isMap ? obj.size : keys.length

    /** @type {undefined | [TokenOrNestedTokens, TokenOrNestedTokens][]} */
    let entries

    if (maxLength) {
      // Pre-allocate the array with the expected size
      entries = new Array(maxLength)
      refStack = Ref.createCheck(refStack, obj)
      const skipUndefined = !isMap && options.ignoreUndefinedProperties

      let i = 0
      for (const key of keys) {
        const value = isMap ? obj.get(key) : obj[key]
        if (skipUndefined && value === undefined) {
          continue
        }
        entries[i++] = [
          objectToTokens(key, options, refStack),
          objectToTokens(value, options, refStack)
        ]
      }

      // Truncate only if properties were skipped
      if (i < maxLength) {
        entries.length = i
      }
    }

    if (!entries?.length) {
      if (options.addBreakTokens === true) {
        return [simpleTokens.emptyMap, new Token(Type.break)]
      }
      return simpleTokens.emptyMap
    }

    sortMapEntries(entries, options)
    if (options.addBreakTokens) {
      return [new Token(Type.map, entries.length), entries, new Token(Type.break)]
    }
    return [new Token(Type.map, entries.length), entries]
  },

  /**
   * Encode a `Tagged` wrapper as a CBOR tag header followed by the encoded
   * form of the wrapped value. The value is recursively tokenised through
   * `objectToTokens()` so any registered `typeEncoders` apply to it.
   *
   * @param {any} obj
   * @param {string} _typ
   * @param {EncodeOptions} options
   * @param {Reference} [refStack]
   * @returns {TokenOrNestedTokens}
   */
  Tagged (obj, _typ, options, refStack) {
    return [
      new Token(Type.tag, obj.tag),
      objectToTokens(obj.value, options, refStack)
    ]
  }
}

typeEncoders.Map = typeEncoders.Object
typeEncoders.Buffer = typeEncoders.Uint8Array
for (const typ of 'Uint8Clamped Uint16 Uint32 Int8 Int16 Int32 BigUint64 BigInt64 Float32 Float64'.split(' ')) {
  typeEncoders[`${typ}Array`] = typeEncoders.DataView
}

/**
 * @param {any} obj
 * @param {EncodeOptions} [options]
 * @param {Reference} [refStack]
 * @returns {TokenOrNestedTokens}
 */
function objectToTokens (obj, options = {}, refStack) {
  const typ = is(obj)
  const customTypeEncoder = (options && options.typeEncoders && /** @type {OptionalTypeEncoder} */ options.typeEncoders[typ]) || typeEncoders[typ]
  if (typeof customTypeEncoder === 'function') {
    const tokens = customTypeEncoder(obj, typ, options, refStack)
    if (tokens != null) {
      return tokens
    }
  }
  const typeEncoder = typeEncoders[typ]
  if (!typeEncoder) {
    throw new Error(`${encodeErrPrefix} unsupported type: ${typ}`)
  }
  return typeEncoder(obj, typ, options, refStack)
}

/*
CBOR key sorting is a mess.

The canonicalisation recommendation from https://tools.ietf.org/html/rfc7049#section-3.9
includes the wording:

> The keys in every map must be sorted lowest value to highest.
> Sorting is performed on the bytes of the representation of the key
> data items without paying attention to the 3/5 bit splitting for
> major types.
> ...
>  *  If two keys have different lengths, the shorter one sorts
      earlier;
>  *  If two keys have the same length, the one with the lower value
      in (byte-wise) lexical order sorts earlier.

1. It is not clear what "bytes of the representation of the key" means: is it
   the CBOR representation, or the binary representation of the object itself?
   Consider the int and uint difference here.
2. It is not clear what "without paying attention to" means: do we include it
   and compare on that? Or do we omit the special prefix byte, (mostly) treating
   the key in its plain binary representation form.

The FIDO 2.0: Client To Authenticator Protocol spec takes the original CBOR
wording and clarifies it according to their understanding.
https://fidoalliance.org/specs/fido-v2.0-rd-20170927/fido-client-to-authenticator-protocol-v2.0-rd-20170927.html#message-encoding

> The keys in every map must be sorted lowest value to highest. Sorting is
> performed on the bytes of the representation of the key data items without
> paying attention to the 3/5 bit splitting for major types. The sorting rules
> are:
>  * If the major types are different, the one with the lower value in numerical
>    order sorts earlier.
>  * If two keys have different lengths, the shorter one sorts earlier;
>  * If two keys have the same length, the one with the lower value in
>    (byte-wise) lexical order sorts earlier.

Some other implementations, such as borc, do a full encode then do a
length-first, byte-wise-second comparison:
https://github.com/dignifiedquire/borc/blob/b6bae8b0bcde7c3976b0f0f0957208095c392a36/src/encoder.js#L358
https://github.com/dignifiedquire/borc/blob/b6bae8b0bcde7c3976b0f0f0957208095c392a36/src/utils.js#L143-L151

This has the benefit of being able to easily handle arbitrary keys, including
complex types (maps and arrays).

We'll opt for the FIDO approach, since it affords some efficies since we don't
need a full encode of each key to determine order and can defer to the types
to determine how to most efficiently order their values (i.e. int and uint
ordering can be done on the numbers, no need for byte-wise, for example).

Recommendation: stick to single key types or you'll get into trouble, and prefer
string keys because it's much simpler that way.
*/

/**
 * @param {TokenOrNestedTokens[]} entries
 * @param {EncodeOptions} options
 */
function sortMapEntries (entries, options) {
  if (options.mapSorter) {
    entries.sort(options.mapSorter)
  }
}

/**
 * @param {(Token|Token[])[]} e1
 * @param {(Token|Token[])[]} e2
 * @returns {number}
 */
function mapSorter (e1, e2) {
  // the key position ([0]) could have a single token or an array
  // almost always it'll be a single token but complex key might get involved
  /* c8 ignore next 2 */
  const keyToken1 = Array.isArray(e1[0]) ? e1[0][0] : e1[0]
  const keyToken2 = Array.isArray(e2[0]) ? e2[0][0] : e2[0]

  // different key types
  if (keyToken1.type !== keyToken2.type) {
    return keyToken1.type.compare(keyToken2.type)
  }

  const major = keyToken1.type.major
  // TODO: handle case where cmp === 0 but there are more keyToken e. complex type)
  const tcmp = cborEncoders[major].compareTokens(keyToken1, keyToken2)
  /* c8 ignore next 5 */
  if (tcmp === 0) {
    // duplicate key or complex type where the first token matched,
    // i.e. a map or array and we're only comparing the opening token
    console.warn('WARNING: complex key types used, CBOR key sorting guarantees are gone')
  }
  return tcmp
}

/**
 * @typedef {Token & { _keyBytes?: Uint8Array }} TokenEx
 *
 * @param {(Token|Token[])[]} e1
 * @param {(Token|Token[])[]} e2
 * @returns {number}
 */
function rfc8949MapSorter (e1, e2) {
  if (e1[0] instanceof Token && e2[0] instanceof Token) {
    const t1 = /** @type {TokenEx} */ (e1[0])
    const t2 = /** @type {TokenEx} */ (e2[0])

    if (!t1._keyBytes) {
      t1._keyBytes = encodeRfc8949(t1.value)
    }

    if (!t2._keyBytes) {
      t2._keyBytes = encodeRfc8949(t2.value)
    }

    return compare(t1._keyBytes, t2._keyBytes)
  }

  throw new Error('rfc8949MapSorter: complex key types are not supported yet')
}

/**
 * @param {any} data
 * @returns {Uint8Array}
 */
function encodeRfc8949 (data) {
  return encodeCustom(data, cborEncoders, rfc8949EncodeOptions)
}

/**
 * @param {ByteWriter} writer
 * @param {TokenOrNestedTokens} tokens
 * @param {TokenTypeEncoder[]} encoders
 * @param {EncodeOptions} options
 */
function tokensToEncoded (writer, tokens, encoders, options) {
  if (Array.isArray(tokens)) {
    for (const token of tokens) {
      tokensToEncoded(writer, token, encoders, options)
    }
  } else {
    encoders[tokens.type.major](writer, tokens, options)
  }
}

// CBOR major type prefixes, cached from Type for hot path performance
const MAJOR_UINT = Type.uint.majorEncoded
const MAJOR_NEGINT = Type.negint.majorEncoded
const MAJOR_BYTES = Type.bytes.majorEncoded
const MAJOR_STRING = Type.string.majorEncoded
const MAJOR_ARRAY = Type.array.majorEncoded

// Simple value bytes (CBOR major type 7 + minor value)
const SIMPLE_FALSE = Type.float.majorEncoded | MINOR_FALSE
const SIMPLE_TRUE = Type.float.majorEncoded | MINOR_TRUE
const SIMPLE_NULL = Type.float.majorEncoded | MINOR_NULL
const SIMPLE_UNDEFINED = Type.float.majorEncoded | MINOR_UNDEFINED

const neg1b = BigInt(-1)
const pos1b = BigInt(1)

/**
 * Check if direct encoding can be used for the given options.
 * Direct encoding bypasses token creation for most values.
 * @param {EncodeOptions} options
 * @returns {boolean}
 */
function canDirectEncode (options) {
  // Cannot use direct encode with addBreakTokens (needs special break token handling).
  // Direct encode checks typeEncoders per-value, falling back to tokens as needed.
  // Maps fall back to token-based encoding for efficient key sorting.
  return options.addBreakTokens !== true
}

/**
 * Direct encode a value to the writer, bypassing token creation for most types.
 * Falls back to token-based encoding for custom type encoders.
 * @param {ByteWriter} writer
 * @param {any} data
 * @param {EncodeOptions} options
 * @param {Reference|undefined} refStack
 */
function directEncode (writer, data, options, refStack) {
  const typ = is(data)

  // Check for custom encoder for THIS specific type
  const customEncoder = options.typeEncoders && options.typeEncoders[typ]
  if (customEncoder) {
    const tokens = customEncoder(data, typ, options, refStack)
    if (tokens != null) {
      // Custom encoder returned tokens, serialize immediately
      tokensToEncoded(writer, tokens, cborEncoders, options)
      return
    }
    // Custom encoder returned null, fall through to default handling
  }

  // Direct encode based on type
  switch (typ) {
    case 'null':
      writer.push([SIMPLE_NULL])
      return

    case 'undefined':
      writer.push([SIMPLE_UNDEFINED])
      return

    case 'boolean':
      writer.push([data ? SIMPLE_TRUE : SIMPLE_FALSE])
      return

    case 'number':
      if (!Number.isInteger(data) || !Number.isSafeInteger(data)) {
        // Float, use token encoder for complex float encoding
        encodeFloat(writer, new Token(Type.float, data), options)
      } else if (data >= 0) {
        encodeUintValue(writer, MAJOR_UINT, data)
      } else {
        // Negative integer
        encodeUintValue(writer, MAJOR_NEGINT, data * -1 - 1)
      }
      return

    case 'bigint':
      if (data >= BigInt(0)) {
        encodeUintValue(writer, MAJOR_UINT, data)
      } else {
        encodeUintValue(writer, MAJOR_NEGINT, data * neg1b - pos1b)
      }
      return

    case 'string': {
      const bytes = fromString(data)
      encodeUintValue(writer, MAJOR_STRING, bytes.length)
      writer.push(bytes)
      return
    }

    case 'Uint8Array':
      encodeUintValue(writer, MAJOR_BYTES, data.length)
      writer.push(data)
      return

    case 'Array':
      if (!data.length) {
        writer.push([MAJOR_ARRAY]) // Empty array: 0x80
        return
      }
      refStack = Ref.createCheck(refStack, data)
      encodeUintValue(writer, MAJOR_ARRAY, data.length)
      for (const elem of data) {
        directEncode(writer, elem, options, refStack)
      }
      return

    case 'Object':
    case 'Map':
      // Maps require key sorting, use token-based encoding for efficiency
      // (pre-encoding all keys for sorting is expensive)
      {
        const tokens = typeEncoders.Object(data, typ, options, refStack)
        tokensToEncoded(writer, tokens, cborEncoders, options)
      }
      return

    default:
    // Fall back to token-based encoding for other types (DataView, TypedArrays, etc.)
    {
      const typeEncoder = typeEncoders[typ]
      if (!typeEncoder) {
        throw new Error(`${encodeErrPrefix} unsupported type: ${typ}`)
      }
      const tokens = typeEncoder(data, typ, options, refStack)
      tokensToEncoded(writer, tokens, cborEncoders, options)
    }
  }
}

/**
 * @param {any} data
 * @param {TokenTypeEncoder[]} encoders
 * @param {EncodeOptions} options
 * @param {Uint8Array} [destination]
 * @returns {Uint8Array}
 */
function encodeCustom (data, encoders, options, destination) {
  // arg ordering is different to encodeInto for backward compatibility
  const hasDest = destination instanceof Uint8Array
  let writeTo = hasDest ? new U8Bl(destination) : defaultWriter

  const tokens = objectToTokens(data, options)
  if (!Array.isArray(tokens) && options.quickEncodeToken) {
    const quickBytes = options.quickEncodeToken(tokens)
    if (quickBytes) {
      if (hasDest) {
        // Copy quick bytes into destination buffer
        writeTo.push(quickBytes)
        return writeTo.toBytes()
      }
      return quickBytes
    }
    const encoder = encoders[tokens.type.major]
    if (encoder.encodedSize) {
      const size = encoder.encodedSize(tokens, options)
      if (!hasDest) {
        writeTo = new Bl(size)
      }
      encoder(writeTo, tokens, options)
      /* c8 ignore next 4 */
      // this would be a problem with encodedSize() functions
      if (writeTo.chunks.length !== 1) {
        throw new Error(`Unexpected error: pre-calculated length for ${tokens} was wrong`)
      }
      return hasDest ? writeTo.toBytes() : asU8A(writeTo.chunks[0])
    }
  }
  writeTo.reset()
  tokensToEncoded(writeTo, tokens, encoders, options)
  return writeTo.toBytes(true)
}

/**
 * @param {any} data
 * @param {EncodeOptions} [options]
 * @returns {Uint8Array}
 */
function encode (data, options) {
  options = Object.assign({}, defaultEncodeOptions, options)

  // Use direct encode path when possible
  if (canDirectEncode(options)) {
    defaultWriter.reset()
    directEncode(defaultWriter, data, options, undefined)
    return defaultWriter.toBytes(true)
  }

  return encodeCustom(data, cborEncoders, options)
}

/**
 * @param {any} data
 * @param {Uint8Array} destination
 * @param {EncodeOptions} [options]
 * @returns {{ written: number }}
 */
function encodeInto (data, destination, options) {
  options = Object.assign({}, defaultEncodeOptions, options)

  // Use direct encode path when possible
  if (canDirectEncode(options)) {
    const writer = new U8Bl(destination)
    directEncode(writer, data, options, undefined)
    return { written: writer.toBytes().length }
  }

  const result = encodeCustom(data, cborEncoders, options, destination)
  return { written: result.length }
}

export { objectToTokens, encode, encodeCustom, encodeInto, Ref }
