renovate/lib/modules/versioning/maven/compare.ts

import { isString } from '@sindresorhus/is';
import { regEx } from '../../../util/regex.ts';
import type { Range, Token } from './types.ts';

const PREFIX_DOT = 'PREFIX_DOT';
const PREFIX_HYPHEN = 'PREFIX_HYPHEN';
const ALPHA_SUFFIX = '-alpha';

const TYPE_NUMBER = 'TYPE_NUMBER';
const TYPE_QUALIFIER = 'TYPE_QUALIFIER';

function iterateChars(
  str: string,
  cb: (p: string | null, n: string | null) => void,
): void {
  let prev = null;
  let next = null;
  for (let i = 0; i < str.length; i += 1) {
    next = str.charAt(i);
    cb(prev, next);
    prev = next;
  }
  cb(prev, null);
}

function isDigit(char: string): boolean {
  return regEx(/^\d$/).test(char);
}

function isLetter(char: string): boolean {
  return regEx(/^[a-z_+]$/i).test(char);
}

function isTransition(prevChar: string, nextChar: string): boolean {
  return (
    (isDigit(prevChar) && isLetter(nextChar)) ||
    (isLetter(prevChar) && isDigit(nextChar))
  );
}

function iterateTokens(versionStr: string, cb: (token: Token) => void): void {
  let currentPrefix = '';
  let currentVal = '';

  function yieldToken(transition = false): void {
    const val = currentVal || '0';
    if (regEx(/^\d+$/).test(val)) {
      cb({
        prefix: currentPrefix,
        type: TYPE_NUMBER,
        val: parseInt(val, 10),
        isTransition: transition,
      });
    } else {
      cb({
        prefix: currentPrefix,
        type: TYPE_QUALIFIER,
        val,
        isTransition: transition,
      });
    }
  }

  iterateChars(versionStr, (prevChar, nextChar) => {
    if (nextChar === null) {
      yieldToken();
    } else if (nextChar === '-') {
      yieldToken();
      currentPrefix = PREFIX_HYPHEN;
      currentVal = '';
    } else if (nextChar === '.') {
      yieldToken();
      currentPrefix = PREFIX_DOT;
      currentVal = '';
    } else if (prevChar === null && (nextChar === 'v' || nextChar === 'V')) {
      currentPrefix = nextChar;
    } else {
      if (currentVal !== '' && isTransition(prevChar!, nextChar)) {
        yieldToken(true);
        currentPrefix = PREFIX_HYPHEN;
        currentVal = nextChar;
      } else if (
        currentVal === '' &&
        (currentPrefix === 'v' || currentPrefix === 'V') &&
        !isDigit(nextChar)
      ) {
        currentVal = currentVal.concat(currentPrefix, nextChar);
        currentPrefix = '';
      } else {
        currentVal = currentVal.concat(nextChar);
      }
    }
  });
}

function isNull(token: Token): boolean {
  const val = token.val;
  return (
    val === 0 ||
    val === '' ||
    val === 'final' ||
    val === 'ga' ||
    val === 'release' ||
    val === 'latest' ||
    val === 'sr'
  );
}

function tokenize(versionStr: string, preserveMinorZeroes = false): Token[] {
  let buf: Token[] = [];
  let result: Token[] = [];
  let leadingZero = true;
  iterateTokens(versionStr.toLowerCase(), (token) => {
    if (token.prefix === PREFIX_HYPHEN || token.type === TYPE_QUALIFIER) {
      buf = [];
    }
    buf.push(token);
    if (!isNull(token)) {
      leadingZero = false;
      result = result.concat(buf);
      buf = [];
    } else if (leadingZero || preserveMinorZeroes) {
      result = result.concat(buf);
      buf = [];
    }
  });
  return result;
}

function nullFor(token: Token): Token {
  return token.type === TYPE_NUMBER
    ? {
        prefix: token.prefix,
        type: TYPE_NUMBER,
        val: 0,
      }
    : {
        prefix: token.prefix,
        type: TYPE_QUALIFIER,
        val: '',
      };
}

function commonOrder(token: Token): number {
  if (token.type === TYPE_QUALIFIER) {
    return 1;
  }
  if (token.prefix === PREFIX_HYPHEN && token.type === TYPE_NUMBER) {
    return 2;
  }
  return 3;
}

export const QualifierTypes = {
  Alpha: 1,
  Beta: 2,
  Milestone: 3,
  RC: 4,
  Snapshot: 5,
  Release: 6,
  SP: 7,
} as const;

export function qualifierType(token: Token): number | null {
  const val = token.val;
  if (val === 'alpha' || (token.isTransition && val === 'a')) {
    return QualifierTypes.Alpha;
  }
  if (val === 'beta' || (token.isTransition && val === 'b')) {
    return QualifierTypes.Beta;
  }
  if (val === 'milestone' || (token.isTransition && val === 'm')) {
    return QualifierTypes.Milestone;
  }
  if (val === 'rc' || val === 'cr' || val === 'preview') {
    return QualifierTypes.RC;
  }
  if (val === 'snapshot' || val === 'snap') {
    return QualifierTypes.Snapshot;
  }
  if (
    val === '' ||
    val === 'final' ||
    val === 'ga' ||
    val === 'release' ||
    val === 'latest' ||
    val === 'sr'
  ) {
    return QualifierTypes.Release;
  }
  if (val === 'sp') {
    return QualifierTypes.SP;
  }
  return null;
}

function qualifierCmp(left: Token, right: Token): number {
  const leftOrder = qualifierType(left);
  const rightOrder = qualifierType(right);
  if (leftOrder && rightOrder) {
    if (leftOrder < rightOrder) {
      return -1;
    }
    if (leftOrder > rightOrder) {
      return 1;
    }
    return 0;
  }

  if (leftOrder && leftOrder < QualifierTypes.Release) {
    return -1;
  }
  if (rightOrder && rightOrder < QualifierTypes.Release) {
    return 1;
  }

  if (left.val < right.val) {
    return -1;
  }
  if (left.val > right.val) {
    return 1;
  }
  return 0;
}

function tokenCmp(left: Token, right: Token): number {
  const leftOrder = commonOrder(left);
  const rightOrder = commonOrder(right);

  if (leftOrder < rightOrder) {
    return -1;
  }
  if (leftOrder > rightOrder) {
    return 1;
  }

  if (left.type === TYPE_NUMBER && right.type === TYPE_NUMBER) {
    if (left.val < right.val) {
      return -1;
    }
    if (left.val > right.val) {
      return 1;
    }
    return 0;
  }

  return qualifierCmp(left, right);
}

function compare(left: string, right: string): number {
  const leftTokens = tokenize(left);
  const rightTokens = tokenize(right);
  const length = Math.max(leftTokens.length, rightTokens.length);
  for (let idx = 0; idx < length; idx += 1) {
    const leftToken = leftTokens[idx] || nullFor(rightTokens[idx]);
    const rightToken = rightTokens[idx] || nullFor(leftTokens[idx]);
    const cmpResult = tokenCmp(leftToken, rightToken);
    if (cmpResult !== 0) {
      return cmpResult;
    }
  }
  return 0;
}

function isVersion(version: unknown): version is string {
  if (!version || !isString(version)) {
    return false;
  }
  if (!regEx(/^[-.a-z_+0-9]+$/i).test(version)) {
    return false;
  }
  if (regEx(/^[.-]/).test(version)) {
    return false;
  }
  if (regEx(/[.-]$/).test(version)) {
    return false;
  }
  if (['latest', 'release'].includes(version.toLowerCase())) {
    return false;
  }
  const tokens = tokenize(version);
  return !!tokens.length;
}

const INCLUDING_POINT = 'INCLUDING_POINT';
const EXCLUDING_POINT = 'EXCLUDING_POINT';

function parseRange(rangeStr: string): Range[] | null {
  function emptyInterval(): Range {
    return {
      leftType: null,
      leftValue: null,
      leftBracket: null,
      rightType: null,
      rightValue: null,
      rightBracket: null,
    };
  }

  const commaSplit = rangeStr.split(regEx(/\s*,\s*/));
  let ranges: Range[] | null = [];
  let interval = emptyInterval();

  commaSplit.forEach((subStr) => {
    if (!ranges) {
      return;
    }
    if (interval.leftType === null) {
      if (regEx(/^\[.*]$/).test(subStr)) {
        const ver = subStr.slice(1, -1);
        ranges.push({
          leftType: INCLUDING_POINT,
          leftValue: ver,
          leftBracket: '[',
          rightType: INCLUDING_POINT,
          rightValue: ver,
          rightBracket: ']',
        });
        interval = emptyInterval();
      } else if (subStr.startsWith('[')) {
        const ver = subStr.slice(1);
        interval.leftType = INCLUDING_POINT;
        interval.leftValue = ver;
        interval.leftBracket = '[';
      } else if (subStr.startsWith('(') || subStr.startsWith(']')) {
        const ver = subStr.slice(1);
        interval.leftType = EXCLUDING_POINT;
        interval.leftValue = ver;
        interval.leftBracket = subStr[0];
      } else {
        ranges = null;
      }
    } else if (subStr.endsWith(']')) {
      const ver = subStr.slice(0, -1);
      interval.rightType = INCLUDING_POINT;
      interval.rightValue = ver;
      interval.rightBracket = ']';
      ranges.push(interval);
      interval = emptyInterval();
    } else if (subStr.endsWith(')') || subStr.endsWith('[')) {
      const ver = subStr.slice(0, -1);
      interval.rightType = EXCLUDING_POINT;
      interval.rightValue = ver;
      interval.rightBracket = subStr.endsWith(')') ? ')' : '[';
      ranges.push(interval);
      interval = emptyInterval();
    } else {
      ranges = null;
    }
  });

  if (interval.leftType) {
    return null;
  } // something like '[1,2],[3'
  if (!ranges?.length) {
    return null;
  }

  const lastIdx = ranges.length - 1;
  let prevValue: string | null = null;
  const result: Range[] = [];
  for (let idx = 0; idx < ranges.length; idx += 1) {
    const range = ranges[idx];
    const { leftType, leftValue, rightType, rightValue } = range;

    if (idx === 0 && leftValue === '') {
      if (leftType === EXCLUDING_POINT && isVersion(rightValue)) {
        prevValue = rightValue;
        result.push({ ...range, leftValue: null });
        continue;
      }
      return null;
    }
    if (idx === lastIdx && rightValue === '') {
      if (rightType === EXCLUDING_POINT && isVersion(leftValue)) {
        if (prevValue && compare(prevValue, leftValue) === 1) {
          return null;
        }
        result.push({ ...range, rightValue: null });
        continue;
      }
      return null;
    }
    if (isVersion(leftValue) && isVersion(rightValue)) {
      if (compare(leftValue, rightValue) === 1) {
        return null;
      }
      if (prevValue && compare(prevValue, leftValue) === 1) {
        return null;
      }
      prevValue = rightValue;
      result.push(range);
      continue;
    }
    return null;
  }
  return result;
}

function isValid(str: string): boolean {
  if (!str) {
    return false;
  }
  return isVersion(str) || !!parseRange(str);
}

function rangeToStr(fullRange: Range[] | null): string | null {
  if (fullRange === null) {
    return null;
  }

  function valToStr(val: string | null): string {
    return val ?? '';
  }

  if (fullRange.length === 1) {
    const { leftBracket, rightBracket, leftValue, rightValue } = fullRange[0];
    if (
      leftValue === rightValue &&
      leftBracket === '[' &&
      rightBracket === ']'
    ) {
      return `[${valToStr(leftValue)}]`;
    }
  }

  const intervals = fullRange.map((val) =>
    [
      val.leftBracket,
      valToStr(val.leftValue),
      ',',
      valToStr(val.rightValue),
      val.rightBracket,
    ].join(''),
  );
  return intervals.join(',');
}

function tokensToStr(tokens: Token[]): string {
  let isTransition: boolean | undefined = false;
  return tokens.reduce((result: string, token: Token) => {
    let prefix: string;
    if (token.prefix === PREFIX_DOT) {
      prefix = '.';
    } else if (token.prefix === PREFIX_HYPHEN) {
      prefix = isTransition === true ? '' : '-';
    } else {
      prefix = token.prefix;
    }
    isTransition = token.isTransition;
    return `${result}${prefix}${token.val}`;
  }, '');
}

function coerceRangeValue(prev: string, next: string): string {
  const prevTokens = tokenize(prev, true);
  const nextTokens = tokenize(next, true);
  const resultTokens = nextTokens.slice(0, prevTokens.length);
  const align = Math.max(0, prevTokens.length - nextTokens.length);
  if (align > 0) {
    resultTokens.push(...prevTokens.slice(prevTokens.length - align));
  }
  return tokensToStr(resultTokens);
}

function incrementRangeValue(value: string): string {
  const tokens = tokenize(value);
  const lastToken = tokens.at(-1)!;
  if (typeof lastToken.val === 'number') {
    lastToken.val += 1;
    return coerceRangeValue(value, tokensToStr(tokens));
  }
  return value;
}

function autoExtendMavenRange(
  currentRepresentation: string,
  newValue: string,
): string | null {
  const range = parseRange(currentRepresentation);
  if (!range) {
    return currentRepresentation;
  }
  function isPoint(vals: Range[]): boolean {
    if (vals.length !== 1) {
      return false;
    }
    const { leftType, leftValue, rightType, rightValue } = vals[0];
    return (
      leftType === 'INCLUDING_POINT' &&
      leftType === rightType &&
      leftValue === rightValue
    );
  }
  if (isPoint(range)) {
    return `[${newValue}]`;
  }

  const interval = [...range].reverse().find((elem) => {
    const { rightType, rightValue } = elem;
    return (
      rightValue === null ||
      (rightType === INCLUDING_POINT && compare(rightValue, newValue) === -1) ||
      (rightType === EXCLUDING_POINT && compare(rightValue, newValue) !== 1)
    );
  });

  if (!interval) {
    return currentRepresentation;
  }

  const { leftValue, rightValue } = interval;
  if (
    leftValue !== null &&
    rightValue !== null &&
    incrementRangeValue(leftValue) === rightValue
  ) {
    // if a range was detected where incrementing the lower value once results in the upper value
    // and the new version is outside the range, construct a new range that follows the same semantic
    // [1,2) / 4.3.2 => [4,5)
    if (compare(newValue, leftValue) !== -1) {
      interval.leftValue = coerceRangeValue(leftValue, newValue);
      interval.rightValue = incrementRangeValue(interval.leftValue);
    }
  } else if (
    leftValue !== null &&
    rightValue !== null &&
    incrementRangeValue(leftValue) + ALPHA_SUFFIX === rightValue
  ) {
    // same as last if, but properly considering Maven ordering specification documented at
    // https://maven.apache.org/pom.html#Version_Order_Specification
    // 4-alpha is smaller than 4.0.0 for example
    // while often people that intend to only match version 1.x use [1,2)
    // this is not correct as it matches various 2.x versions, mostly pre-versions
    // so the correct range definition would be [1,2-alpha) as nothing
    // starting with 2 can be lower than 2-alpha in Maven version ordering logic
    //
    // so this if handles the conceptually same case as the last if
    // just for the case when proper Maven ranges are used
    // [1,2-alpha) / 4.3.2 => [4,5-alpha)
    interval.leftValue = coerceRangeValue(leftValue, newValue);
    interval.rightValue =
      incrementRangeValue(interval.leftValue) + ALPHA_SUFFIX;
  } else if (rightValue !== null) {
    if (interval.rightType === INCLUDING_POINT) {
      const tokens = tokenize(rightValue);
      const lastToken = tokens.at(-1)!;
      if (typeof lastToken.val === 'number') {
        interval.rightValue = coerceRangeValue(rightValue, newValue);
      } else {
        interval.rightValue = newValue;
      }
    } else {
      interval.rightValue = incrementRangeValue(
        coerceRangeValue(rightValue, newValue),
      );
    }
  } else if (leftValue !== null) {
    interval.leftValue = coerceRangeValue(leftValue, newValue);
  }

  return rangeToStr(range);
}

function isSubversion(majorVersion: string, minorVersion: string): boolean {
  const majorTokens = tokenize(majorVersion);
  const minorTokens = tokenize(minorVersion);

  let result = true;
  const len = majorTokens.length;
  for (let idx = 0; idx < len; idx += 1) {
    const major = majorTokens[idx];
    const minor = minorTokens[idx] || nullFor(majorTokens[idx]);
    const cmpResult = tokenCmp(major, minor);
    if (cmpResult !== 0) {
      result = false;
      break;
    }
  }
  return result;
}

export {
  EXCLUDING_POINT,
  INCLUDING_POINT,
  PREFIX_DOT,
  PREFIX_HYPHEN,
  TYPE_NUMBER,
  TYPE_QUALIFIER,
  autoExtendMavenRange,
  compare,
  isSubversion,
  isValid,
  isVersion,
  isVersion as isSingleVersion,
  parseRange,
  rangeToStr,
  tokenize,
};