licenses.ts

/**
 * @file SPDX license parsing and analysis utilities.
 */

import { LOOP_SENTINEL } from '../constants/sentinels'
import { getCopyLeftLicenses } from '../constants/licenses'
import spdxCorrect from '../external/spdx-correct'
import spdxExpParse from '../external/spdx-expression-parse'
import { hasOwn } from '../objects/predicates'
import { normalizePath } from '../paths/normalize'

import type { LicenseNode } from './types'

import { ErrorCtor } from '../primordials/error'

import { MapCtor } from '../primordials/map-set'

import { RegExpPrototypeExec } from '../primordials/regexp'
const copyLeftLicenses = getCopyLeftLicenses()

import { getNodePath } from '../node/path'

const BINARY_OPERATION_NODE_TYPE = 'BinaryOperation'
const LICENSE_NODE_TYPE = 'License'

const fileReferenceRegExp = /^SEE LICEN[CS]E IN (.+)$/

// Duplicated from spdx-expression-parse - AST node types.
export interface SpdxLicenseNode {
  license: string
  plus?: boolean | undefined
  exception?: string | undefined
}

export interface SpdxBinaryOperationNode {
  left: SpdxLicenseNode | SpdxBinaryOperationNode
  conjunction: 'and' | 'or'
  right: SpdxLicenseNode | SpdxBinaryOperationNode
}

export type SpdxAstNode = SpdxLicenseNode | SpdxBinaryOperationNode

// Internal AST node types with type discriminator.
export interface InternalLicenseNode extends SpdxLicenseNode {
  type: 'License'
}

export interface InternalBinaryOperationNode {
  type: 'BinaryOperation'
  left: InternalLicenseNode | InternalBinaryOperationNode
  conjunction: 'and' | 'or'
  right: InternalLicenseNode | InternalBinaryOperationNode
}

export type InternalAstNode = InternalLicenseNode | InternalBinaryOperationNode

export interface LicenseVisitor {
  License?: (
    node: InternalLicenseNode,
    parent?: InternalAstNode,
  ) => boolean | undefined
  BinaryOperation?: (
    node: InternalBinaryOperationNode,
    parent?: InternalAstNode,
  ) => boolean | undefined
}

/**
 * Collect licenses that are incompatible (copyleft).
 *
 * @example
 *   ;```typescript
 *   const nodes = [{ license: 'MIT' }, { license: 'GPL-3.0' }]
 *   const incompatible = collectIncompatibleLicenses(nodes)
 *   // incompatible contains only the GPL-3.0 node
 *   ```
 */
export function collectIncompatibleLicenses(
  licenseNodes: LicenseNode[],
): LicenseNode[] {
  const result = []
  for (let i = 0, { length } = licenseNodes; i < length; i += 1) {
    const node = licenseNodes[i]
    if (node && copyLeftLicenses.has(node.license)) {
      result.push(node)
    }
  }
  return result
}

/**
 * Collect warnings from license nodes.
 *
 * @example
 *   ;```typescript
 *   const nodes = [{ license: 'UNLICENSED' }]
 *   collectLicenseWarnings(nodes) // ['Package is unlicensed']
 *   ```
 */
export function collectLicenseWarnings(licenseNodes: LicenseNode[]): string[] {
  const warnings = new MapCtor()
  for (let i = 0, { length } = licenseNodes; i < length; i += 1) {
    const node = licenseNodes[i]
    if (!node) {
      continue
    }
    const { license } = node
    if (license === 'UNLICENSED') {
      warnings.set('UNLICENSED', 'Package is unlicensed')
    } else if (node.inFile !== undefined) {
      warnings.set('IN_FILE', `License terms specified in ${node.inFile}`)
    }
  }
  return [...warnings.values()]
}

/**
 * Create an AST node from a raw node.
 *
 * @example
 *   ;```typescript
 *   const raw = { license: 'MIT' }
 *   const node = createAstNode(raw)
 *   // node.type === 'License'
 *   ```
 */
export function createAstNode(rawNode: SpdxAstNode): InternalAstNode {
  return hasOwn(rawNode, 'license')
    ? createLicenseNode(rawNode as SpdxLicenseNode)
    : createBinaryOperationNode(rawNode as SpdxBinaryOperationNode)
}

/**
 * Create a binary operation AST node.
 *
 * @example
 *   ;```typescript
 *   const raw = {
 *     left: { license: 'MIT' },
 *     conjunction: 'OR' as const,
 *     right: { license: 'Apache-2.0' },
 *   }
 *   const node = createBinaryOperationNode(raw)
 *   // node.type === 'BinaryOperation'
 *   ```
 */
export function createBinaryOperationNode(
  rawNodeParam: SpdxBinaryOperationNode,
): InternalBinaryOperationNode {
  let left: InternalAstNode | undefined
  let right: InternalAstNode | undefined
  let rawLeft: SpdxAstNode | undefined = rawNodeParam.left
  let rawRight: SpdxAstNode | undefined = rawNodeParam.right
  const { conjunction } = rawNodeParam
  // Clear the reference to help with memory management.
  return {
    __proto__: null,
    type: BINARY_OPERATION_NODE_TYPE as 'BinaryOperation',
    get left() {
      if (left === undefined) {
        left = createAstNode(rawLeft as SpdxAstNode)
        rawLeft = undefined
      }
      return left
    },
    conjunction,
    get right() {
      if (right === undefined) {
        right = createAstNode(rawRight as SpdxAstNode)
        rawRight = undefined
      }
      return right
    },
  } as InternalBinaryOperationNode
}

/**
 * Create a license AST node.
 *
 * @example
 *   ;```typescript
 *   const node = createLicenseNode({ license: 'MIT' })
 *   // node.type === 'License' && node.license === 'MIT'
 *   ```
 */
export function createLicenseNode(
  rawNode: SpdxLicenseNode,
): InternalLicenseNode {
  return {
    __proto__: null,
    ...rawNode,
    type: LICENSE_NODE_TYPE as 'License',
  } as InternalLicenseNode
}

/**
 * Parse an SPDX license expression into an AST.
 *
 * @example
 *   ;```typescript
 *   const ast = parseSpdxExp('MIT OR Apache-2.0')
 *   // ast is a BinaryOperation node with MIT and Apache-2.0 leaves
 *   ```
 */
export function parseSpdxExp(spdxExp: string): SpdxAstNode | undefined {
  // spdxExpParse is imported at the top
  try {
    return spdxExpParse(spdxExp)
  } catch {}
  // spdxCorrect is imported at the top
  const corrected = spdxCorrect(spdxExp)
  return corrected ? spdxExpParse(corrected) : undefined
}

/**
 * Parse package license field into structured license nodes.
 *
 * @example
 *   ;```typescript
 *   const nodes = resolvePackageLicenses('MIT', '/tmp/my-project')
 *   // [{ license: 'MIT' }]
 *   ```
 */
export function resolvePackageLicenses(
  licenseFieldValue: string,
  where: string,
): LicenseNode[] {
  // Based off of validate-npm-package-license which npm, by way of normalize-package-data,
  // uses to validate license field values:
  // https://github.com/kemitchell/validate-npm-package-license.js/blob/v3.0.4/index.js#L40-L41
  if (
    licenseFieldValue === 'UNLICENCED' ||
    licenseFieldValue === 'UNLICENSED'
  ) {
    return [{ license: 'UNLICENSED' }]
  }
  // Match "SEE LICENSE IN <relativeFilepathToLicense>"
  // https://github.com/kemitchell/validate-npm-package-license.js/blob/v3.0.4/index.js#L48-L53
  const match = RegExpPrototypeExec(fileReferenceRegExp, licenseFieldValue)
  if (match) {
    const path = getNodePath()
    return [
      {
        license: licenseFieldValue,
        inFile: normalizePath(path.relative(where, match[1] || '')),
      },
    ]
  }
  const licenseNodes: InternalLicenseNode[] = []
  const ast = parseSpdxExp(licenseFieldValue)
  if (ast) {
    // SPDX expressions are valid, too except if they contain "LicenseRef" or
    // "DocumentRef". If the licensing terms cannot be described with standardized
    // SPDX identifiers, then the terms should be put in a file in the package
    // and the license field should point users there, e.g. "SEE LICENSE IN LICENSE.txt".
    // https://github.com/kemitchell/validate-npm-package-license.js/blob/v3.0.4/index.js#L18-L24
    visitLicenses(ast, {
      License(node: InternalLicenseNode) {
        const { license } = node
        if (
          license.startsWith('LicenseRef') ||
          license.startsWith('DocumentRef')
        ) {
          licenseNodes.length = 0
          return false
        }
        licenseNodes.push(node)
      },
    })
  }
  return licenseNodes
}

/**
 * Traverse SPDX license AST and invoke visitor callbacks for each node.
 *
 * @example
 *   ;```typescript
 *   const ast = parseSpdxExp('MIT OR Apache-2.0')
 *   const licenses: string[] = []
 *   if (ast) {
 *     visitLicenses(ast, {
 *       License(node) {
 *         licenses.push(node.license)
 *       },
 *     })
 *   }
 *   // licenses === ['MIT', 'Apache-2.0']
 *   ```
 */
export function visitLicenses(ast: SpdxAstNode, visitor: LicenseVisitor): void {
  const queue: Array<[InternalAstNode, InternalAstNode | undefined]> = [
    [createAstNode(ast), undefined],
  ]
  let pos = 0
  let { length: queueLength } = queue
  while (pos < queueLength) {
    if (pos === LOOP_SENTINEL) {
      throw new ErrorCtor(
        'Detected infinite loop in ast crawl of visitLicenses',
      )
    }
    // AST nodes can be a license node which looks like
    //   {
    //     license: string
    //     plus?: boolean
    //     exception?: string
    //   }
    // or a binary operation node which looks like
    //   {
    //     left: License | BinaryOperation
    //     conjunction: string
    //     right: License | BinaryOperation
    //   }
    const { 0: node, 1: parent } = queue[pos++] as [
      InternalBinaryOperationNode | InternalLicenseNode,
      InternalBinaryOperationNode | null,
    ]
    const { type } = node
    const visitorRecord = visitor as Record<string, unknown>
    if (typeof visitorRecord[type] === 'function' && hasOwn(visitor, type)) {
      if (type === LICENSE_NODE_TYPE) {
        const licenseVisitor = visitorRecord['License']
        if (
          typeof licenseVisitor === 'function' &&
          licenseVisitor(node as InternalLicenseNode, parent) === false
        ) {
          break
        }
      } else if (type === BINARY_OPERATION_NODE_TYPE) {
        const binaryOpVisitor = visitorRecord['BinaryOperation']
        if (
          typeof binaryOpVisitor === 'function' &&
          binaryOpVisitor(node as InternalBinaryOperationNode, parent) === false
        ) {
          break
        }
      }
    }
    if (type === BINARY_OPERATION_NODE_TYPE) {
      queue[queueLength++] = [node.left, node]
      queue[queueLength++] = [node.right, node]
    }
  }
}