government / ast / oid.go

@ de62e8f8076f6010f59527991dbc61d7625a603e | history


package ast

import (
	"crypto/x509"
	"errors"
	"fmt"
	"strings"
	"unicode/utf8"

	"government/internal/der"
	"government/sexpr"
)

// Root is the arc every node OID starts with.
const Root = "2.25.9665536045854453410170579537759926404"

// Namespace is an OID's first arc after Root. It says how to read the
// payload, so the same text can be a symbol, a number or a string.
type Namespace uint64

const (
	NSBuiltin Namespace = iota
	NSSymbol
	NSInt
	NSFloat
	NSString
)

var nsNames = []string{"builtin", "symbol", "integer", "float", "string"}

func (ns Namespace) String() string {
	if ns < Namespace(len(nsNames)) {
		return nsNames[ns]
	}
	return fmt.Sprintf("namespace %d", uint64(ns))
}

// rootBytes is Root in DER. Encoding appends arcs to it and decoding strips
// it, working on bytes because x509.OID has no way to read its arcs back
// and Root is too large for OIDFromInts.
var rootBytes = func() []byte {
	oid, err := x509.ParseOID(Root)
	if err != nil {
		panic(err)
	}
	b, err := oid.MarshalBinary()
	if err != nil {
		panic(err)
	}
	return b
}()

// EncodeOID builds the OID Root.ns.id.payload. For a builtin, text is its
// name and the payload is its code; otherwise the payload is text's code
// points.
func EncodeOID(ns Namespace, id uint64, text string) (x509.OID, error) {
	if id == 0 {
		return x509.OID{}, errors.New("node id must be positive")
	}
	var payload []uint64
	if ns == NSBuiltin {
		code, ok := codeByName[text]
		if !ok {
			return x509.OID{}, fmt.Errorf("%q is not a builtin", text)
		}
		payload = []uint64{code}
	} else {
		if !utf8.ValidString(text) {
			return x509.OID{}, fmt.Errorf("%s %q is not valid UTF-8", ns, text)
		}
		if err := checkPayload(ns, text); err != nil {
			return x509.OID{}, err
		}
		for _, r := range text {
			payload = append(payload, uint64(r))
		}
	}

	b := append([]byte{}, rootBytes...)
	b = der.AppendArc(b, uint64(ns))
	b = der.AppendArc(b, id)
	for _, arc := range payload {
		b = der.AppendArc(b, arc)
	}
	var oid x509.OID
	if err := oid.UnmarshalBinary(b); err != nil {
		return x509.OID{}, err
	}
	return oid, nil
}

// DecodeOID is EncodeOID's inverse. Its input comes from an untrusted
// certificate, so every rule EncodeOID follows is checked again here.
func DecodeOID(oid x509.OID) (ns Namespace, id uint64, text string, err error) {
	b, err := oid.MarshalBinary()
	if err != nil {
		return 0, 0, "", err
	}
	// An arc's last byte is below 0x80, so a byte prefix match ends on an
	// arc boundary.
	rest, ok := strings.CutPrefix(string(b), string(rootBytes))
	if !ok {
		return 0, 0, "", fmt.Errorf("OID %s is not under %s", oid, Root)
	}
	arcs, err := readArcs([]byte(rest))
	if err != nil {
		return 0, 0, "", fmt.Errorf("OID %s: %w", oid, err)
	}
	if len(arcs) < 2 {
		return 0, 0, "", fmt.Errorf("OID %s has no node id", oid)
	}
	ns, id, payload := Namespace(arcs[0]), arcs[1], arcs[2:]
	if ns > NSString {
		return 0, 0, "", fmt.Errorf("OID %s: unknown %s", oid, ns)
	}
	if id == 0 {
		return 0, 0, "", fmt.Errorf("OID %s: node id must be positive", oid)
	}

	if ns == NSBuiltin {
		if len(payload) != 1 {
			return 0, 0, "", fmt.Errorf("OID %s: a builtin has exactly one payload arc, got %d", oid, len(payload))
		}
		name, ok := nameByCode[payload[0]]
		if !ok {
			return 0, 0, "", fmt.Errorf("OID %s: unknown builtin code %d", oid, payload[0])
		}
		return ns, id, name, nil
	}

	var sb strings.Builder
	for _, arc := range payload {
		// ValidRune rejects both surrogates and values past U+10FFFF.
		if arc > utf8.MaxRune || !utf8.ValidRune(rune(arc)) {
			return 0, 0, "", fmt.Errorf("OID %s: arc %d is not a Unicode code point", oid, arc)
		}
		sb.WriteRune(rune(arc))
	}
	text = sb.String()
	if err := checkPayload(ns, text); err != nil {
		return 0, 0, "", fmt.Errorf("OID %s: %w", oid, err)
	}
	return ns, id, text, nil
}

// checkPayload applies the reader's grammar, so a text decodes as a symbol
// or number exactly when the same text in source would read as one.
func checkPayload(ns Namespace, text string) error {
	switch ns {
	case NSSymbol:
		if text == "" {
			return errors.New("empty symbol")
		}
		if IsBuiltin(text) {
			return fmt.Errorf("symbol %q is a builtin name", text)
		}
		if _, isNumber, _ := sexpr.ParseNumber(text); isNumber {
			return fmt.Errorf("symbol %q reads as a number", text)
		}
	case NSInt:
		v, _, err := sexpr.ParseNumber(text)
		if err != nil {
			return err
		}
		if _, ok := v.(sexpr.Int); !ok {
			return fmt.Errorf("%q is not an integer", text)
		}
	case NSFloat:
		v, _, err := sexpr.ParseNumber(text)
		if err != nil {
			return err
		}
		if _, ok := v.(sexpr.Float); !ok {
			return fmt.Errorf("%q is not a float", text)
		}
	case NSString:
	default:
		return fmt.Errorf("unknown %s", ns)
	}
	return nil
}

func readArcs(b []byte) ([]uint64, error) {
	var arcs []uint64
	for len(b) > 0 {
		var arc uint64
		for i := 0; ; i++ {
			if i == len(b) {
				return nil, errors.New("truncated arc")
			}
			if arc > (1<<64-1)>>7 {
				return nil, errors.New("arc does not fit in 64 bits")
			}
			arc = arc<<7 | uint64(b[i]&0x7f)
			if b[i]&0x80 == 0 {
				b = b[i+1:]
				break
			}
		}
		arcs = append(arcs, arc)
	}
	return arcs, nil
}