unicode_collation.nim

unicode_collation.nim

# MIT License
# 
# Copyright (c) 2026 Esteban Castro Borsani
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

# Implements https://www.unicode.org/reports/tr10/
# General comparison (no lang tailoring)
# The comparison is incremental, without building the full keys;
# so at some point it can be made allocation free

# XXX DUCET table must add Tibetan extra code points to make it well formed
#     see https://www.unicode.org/reports/tr10/#Well_Formed_DUCET

import unicode
import pkg/unicodedb/collation
import pkg/normalize

proc collationLevel(s: openArray[Rune], shift: bool, level: int, afterVar: var bool): seq[uint16] =
  if not shift:
    if level == 1:
      for x in collationElements(s):
        if x.level1 != 0:
          result.add x.level1
    elif level == 2:
      for x in collationElements(s):
        if x.level2 != 0:
          result.add x.level2
    elif level == 3:
      for x in collationElements(s):
        if x.level3 != 0:
          result.add x.level3
    else:
      doAssert false
  else:
    if level == 1:
      for x in collationElements(s):
        if not x.shifted and x.level1 != 0:
          result.add x.level1
    elif level == 2:
      for x in collationElements(s):
        if x.level1 == 0 and x.level2 == 0 and x.level3 == 0:
          discard
        elif x.shifted:
          afterVar = true
        elif x.level1 != 0:
          afterVar = false
          if x.level2 != 0:
            result.add x.level2
        elif not afterVar:
          if x.level2 != 0:
            result.add x.level2
    elif level == 3:  # same as lvl 2
      for x in collationElements(s):
        if x.level1 == 0 and x.level2 == 0 and x.level3 == 0:
          discard
        elif x.shifted:
          afterVar = true
        elif x.level1 != 0:
          afterVar = false
          if x.level3 != 0:
            result.add x.level3
        elif not afterVar:
          if x.level3 != 0:
            result.add x.level3
    else:
      doAssert level == 4
      for x in collationElements(s):
        if x.level1 == 0 and x.level2 == 0 and x.level3 == 0:
          discard
        elif x.shifted:
          afterVar = true
          result.add x.level1
        elif x.level1 != 0:
          afterVar = false
          result.add 0xFFFF
        elif not afterVar:
          result.add 0xFFFF

proc hasCollation(s: openArray[Rune]): bool =
  for x in collationElements(s):
    return true
  false

proc collationKeyLen(s: string, start: int): int =
  var start = start
  var rns = default(array[collationMaxKeyLen, Rune])
  for i in 0 ..< collationMaxKeyLen:
    if start >= s.len:
      return i
    fastRuneAt(s, start, rns[i])
    if not hasCollation(toOpenArray(rns, 0, i)):
      return i
  collationMaxKeyLen

proc consume(s: string, i: var int, buff: var seq[uint16], shift: bool, level: int, afterVar: var bool) =
  buff.setLen 0
  var rns = default(array[collationMaxKeyLen, Rune])
  while i < s.len:
    let L = collationKeyLen(s, i)
    if L > 0:
      for ii in 0 ..< L:
        fastRuneAt(s, i, rns[ii])
      buff.add collationLevel(toOpenArray(rns, 0, L-1), shift, level, afterVar)
      if buff.len > 0:
        break
    else:
      fastRuneAt(s, i, rns[0])

proc unicodeCmp(a, b: string, shift: bool, level: int): int {.raises: [].} =
  var buffA = default(seq[uint16])
  var buffB = default(seq[uint16])
  var ai = 0
  var bi = 0
  var bai = 0
  var bbi = 0
  var afterVarA = false
  var afterVarB = false
  while true:
    if bai >= buffA.len:
      consume(a, ai, buffA, shift, level, afterVarA)
      bai = 0
    if bbi >= buffB.len:
      consume(b, bi, buffB, shift, level, afterVarB)
      bbi = 0
    if buffA.len == 0 or buffB.len == 0:
      break
    if buffA[bai] < buffB[bbi]:
      return -1
    if buffA[bai] > buffB[bbi]:
      return 1
    inc bai
    inc bbi
  if buffA.len == 0 and buffB.len == 0:
    0
  elif buffA.len > 0:
    1
  else:
    -1

proc unicodeCmp(a, b: string, shift = false): int {.raises: [].} =
  let a = toNfd(a)
  let b = toNfd(b)
  var ret = 0
  if (ret = unicodeCmp(a, b, shift, 1); ret != 0):
    ret
  elif (ret = unicodeCmp(a, b, shift, 2); ret != 0):
    ret
  elif (ret = unicodeCmp(a, b, shift, 3); ret != 0):
    ret
  elif shift and (ret = unicodeCmp(a, b, shift, 4); ret != 0):
    ret
  else:
    cmp(a, b)

when isMainModule:
  # Primary differences
  doAssert unicodeCmp("a", "b") < 0
  doAssert unicodeCmp("b", "a") > 0

  doAssert unicodeCmp("abc", "abd") < 0
  doAssert unicodeCmp("abd", "abc") > 0

  doAssert unicodeCmp("α", "β") < 0
  doAssert unicodeCmp("β", "α") > 0

  # Secondary differences (accents)
  doAssert unicodeCmp("e", "é") < 0
  doAssert unicodeCmp("é", "e") > 0

  doAssert unicodeCmp("a", "á") < 0
  doAssert unicodeCmp("á", "a") > 0

  doAssert unicodeCmp("resume", "résumé") < 0
  doAssert unicodeCmp("résumé", "resume") > 0

  # Tertiary differences (case)
  doAssert unicodeCmp("a", "A") < 0
  doAssert unicodeCmp("A", "a") > 0

  doAssert unicodeCmp("café", "CAFÉ") < 0
  doAssert unicodeCmp("CAFÉ", "café") > 0

  # Canonical equivalence
  doAssert unicodeCmp("é", "e\u0301") == 0
  doAssert unicodeCmp("e\u0301", "é") == 0

  doAssert unicodeCmp("Å", "A\u030A") == 0
  doAssert unicodeCmp("A\u030A", "Å") == 0

  # Prefixes
  doAssert unicodeCmp("a", "aa") < 0
  doAssert unicodeCmp("aa", "a") > 0

  doAssert unicodeCmp("café", "cafés") < 0
  doAssert unicodeCmp("cafés", "café") > 0

  # Combining mark canonical ordering
  doAssert unicodeCmp(
    "a\u0301\u0323",
    "a\u0323\u0301"
  ) == 0

  # Ignorables (assuming DUCET default-ignorable handling)
  doAssert unicodeCmp("abc", "a\u200Dbc") < 0
  doAssert unicodeCmp("a\u200Dbc", "abc") > 0

  doAssert unicodeCmp("test", "te\u00ADst") < 0
  doAssert unicodeCmp("te\u00ADst", "test") > 0

  # Non-Latin sanity checks
  doAssert unicodeCmp("한", "힣") < 0
  doAssert unicodeCmp("힣", "한") > 0

  # Identical-level tie-breaks
  doAssert unicodeCmp("abc", "abc\u200D") < 0
  doAssert unicodeCmp("abc\u200D", "abc") > 0

  doAssert unicodeCmp("a-b", "ab-") < 0
  doAssert unicodeCmp("ab-", "a-b") > 0

  doAssert unicodeCmp("a b", "ab ") < 0
  doAssert unicodeCmp("ab ", "a b") > 0

  doAssert unicodeCmp("-\u0301a", "-a", shift = true) > 0
  doAssert unicodeCmp("-a", "-\u0301a", shift = true) < 0
  doAssert unicodeCmp("ab", "a-c", shift = true) < 0
  doAssert unicodeCmp("a-c", "ab", shift = true) > 0
  doAssert unicodeCmp("ab", "a c", shift = true) < 0
  doAssert unicodeCmp("a c", "ab", shift = true) > 0
  doAssert unicodeCmp("a-c", "ab", shift = false) < 0
  doAssert unicodeCmp("ab", "a-c", shift = false) > 0

  echo "ok"