cases/gen_trieval.go

// Copyright 2014 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// +build ignore

package main

// This file contains definitions for interpreting the trie value of the case
// trie generated by "go run gen*.go". It is shared by both the generator
// program and the resultant package. Sharing is achieved by the generator
// copying gen_trieval.go to trieval.go and changing what's above this comment.

// info holds case information for a single rune. It is the value returned
// by a trie lookup. Most mapping information can be stored in a single 16-bit
// value. If not, for example when a rune is mapped to multiple runes, the value
// stores some basic case data and an index into an array with additional data.
//
// The per-rune values have the following format:
//
//   if (exception) {
//     15..5  unsigned exception index
//         4  unused
//   } else {
//     15..7  XOR pattern or index to XOR pattern for case mapping
//         6  index: interpret the XOR pattern as an index
//      5..4  CCC: zero (normal or break), above or other
//   }
//      3  exception: interpret this value as an exception index
//   2..0  case mode
//
// For the non-exceptional cases, a rune must be either uncased, lowercase or
// uppercase. If the rune is cased, the XOR pattern maps either a lowercase
// rune to uppercase or an uppercase rune to lowercase (applied to the 10
// least-significant bits of the rune).
//
// See the definitions below for a more detailed description of the various
// bits.
type info uint16

const (
	casedMask      = 0x0003
	fullCasedMask  = 0x0007
	ignorableMask  = 0x0006
	ignorableValue = 0x0004

	exceptionBit     = 1 << 3
	exceptionShift   = 5
	numExceptionBits = 11

	xorIndexBit = 1 << 6
	xorShift    = 7

	// There is no mapping if all xor bits and the exception bit are zero.
	hasMappingMask = 0xffc0 | exceptionBit
)

// The case mode bits encodes the case type of a rune. This includes uncased,
// title, upper and lower case and case ignorable. (For a definition of these
// terms see Chapter 3 of The Unicode Standard Core Specification.) In some rare
// cases, a rune can be both cased and case-ignorable. This is encoded by
// cIgnorableCased. A rune of this type is always lower case. Some runes are
// cased while not having a mapping.
//
// A common pattern for scripts in the Unicode standard is for upper and lower
// case runes to alternate for increasing rune values (e.g. the accented Latin
// ranges starting from U+0100 and U+1E00 among others andsome Cyrillic
// characters). We use this property by defining a cXORCase mode, where the case
// mode (always upper or lower case) is derived from the rune value. As the XOR
// pattern for case mappings is often identical for successive runes, using
// cXORCase can result in large series of identical trie values. This, in turn,
// allows us to better compress the trie blocks.
const (
	cUncased          info = iota // 000
	cTitle                        // 001
	cLower                        // 010
	cUpper                        // 011
	cIgnorableUncased             // 100
	cIgnorableCased               // 101 // lower case if mappings exist
	cXORCase                      // 11x // case is cLower | ((rune&1) ^ x)

	maxCaseMode = cUpper
)

func (c info) isCased() bool {
	return c&casedMask != 0
}

func (c info) isCaseIgnorable() bool {
	return c&ignorableMask == ignorableValue
}

func (c info) isCaseIgnorableAndNonBreakStarter() bool {
	return c&(fullCasedMask|cccMask) == (ignorableValue | cccZero)
}

func (c info) isNotCasedAndNotCaseIgnorable() bool {
	return c&fullCasedMask == 0
}

func (c info) isCaseIgnorableAndNotCased() bool {
	return c&fullCasedMask == cIgnorableUncased
}

// The case mapping implementation will need to know about various Canonical
// Combining Class (CCC) values. We encode two of these in the trie value:
// cccZero (0) and cccAbove (230). If the value is cccOther, it means that
// CCC(r) > 0, but not 230. A value of cccBreak means that CCC(r) == 0 and that
// the rune also has the break category Break (see below).
const (
	cccBreak info = iota << 4
	cccZero
	cccAbove
	cccOther

	cccMask = cccBreak | cccZero | cccAbove | cccOther
)

func (c info) cccVal() info {
	if c&exceptionBit != 0 {
		return cccZero
	}
	return c & cccMask
}

func (c info) cccType() info {
	ccc := c.cccVal()
	if ccc <= cccZero {
		return cccZero
	}
	return ccc
}

const (
	starter       = 0
	above         = 230
	iotaSubscript = 240
)

// TODO: Implement full Unicode breaking algorithm:
// 1) Implement breaking in separate package.
// 2) Use the breaker here.
// 3) Compare table size and performance of using the more generic breaker.
//
// Note that we can extend the current algorithm to be much more accurate. This
// only makes sense, though, if the performance and/or space penalty of using
// the generic breaker is big. Extra data will only be needed for non-cased
// runes, which means there are sufficient bits left in the caseType.
// Also note that the standard breaking algorithm doesn't always make sense
// for title casing. For example, a4a -> A4a, but a"4a -> A"4A (where " stands
// for modifier \u0308).
// ICU prohibits breaking in such cases as well.

// For the purpose of title casing we use an approximation of the Unicode Word
// Breaking algorithm defined in Annex #29:
// http://www.unicode.org/reports/tr29/#Default_Grapheme_Cluster_Table.
//
// For our approximation, we group the Word Break types into the following
// categories, with associated rules:
//
// 1) Letter:
//    ALetter, Hebrew_Letter, Numeric, ExtendNumLet, Extend.
//    Rule: Never break between consecutive runes of this category.
//
// 2) Mid:
//    Format, MidLetter, MidNumLet, Single_Quote.
//    (Cf. case-ignorable: MidLetter, MidNumLet or cat is Mn, Me, Cf, Lm or Sk).
//    Rule: Don't break between Letter and Mid, but break between two Mids.
//
// 3) Break:
//    Any other category, including NewLine, CR, LF and Double_Quote. These
//    categories should always result in a break between two cased letters.
//    Rule: Always break.
//
// Note 1: the Katakana and MidNum categories can, in esoteric cases, result in
// preventing a break between two cased letters. For now we will ignore this
// (e.g. [ALetter] [ExtendNumLet] [Katakana] [ExtendNumLet] [ALetter] and
// [ALetter] [Numeric] [MidNum] [Numeric] [ALetter].)
//
// Note 2: the rule for Mid is very approximate, but works in most cases. To
// improve, we could store the categories in the trie value and use a FA to
// manage breaks. See TODO comment above.
//
// Note 3: according to the spec, it is possible for the Extend category to
// introduce breaks between other categories grouped in Letter. However, this
// is undesirable for our purposes. ICU prevents breaks in such cases as well.

// isBreak returns whether this rune should introduce a break.
func (c info) isBreak() bool {
	return c.cccVal() == cccBreak
}

// isLetter returns whether the rune is of break type ALetter, Hebrew_Letter,
// Numeric, ExtendNumLet, or Extend.
func (c info) isLetter() bool {
	ccc := c.cccVal()
	if ccc == cccZero {
		return !c.isCaseIgnorable()
	}
	return ccc != cccBreak
}

// The exceptions slice holds data that does not fit in a normal info entry.
// The entry is pointed to by the exception index in an entry. It has the
// following format:
//
// Header:
// byte 0: // TODO: case folding not implemented yet.
//      7  conditional case folding
//      6  conditional special casing
//   6..3  length of case folding
//   2..0  length of closure mapping (up to 7).
//
// byte 1:
//   7..6  unused
//   5..3  length of 1st mapping of case type
//   2..0  length of 2nd mapping of case type
//
//   case     1st    2nd
//   lower -> upper, title
//   upper -> lower, title
//   title -> lower, upper
//
// Lengths with the value 0x7 indicate no value and implies no change.
// A length of 0 indicates a mapping to zero-length string.
//
// Body bytes:
//   lowercase mapping bytes
//   uppercase mapping bytes
//   titlecase mapping bytes
//   case folding bytes
//   closure mapping bytes
//
// Fallbacks:
//   missing fold  -> lower
//   missing title -> upper
//   all missing   -> original rune
//
// exceptions starts with a dummy byte to enforce that there is no zero index
// value.
const (
	lengthMask = 0x07
	lengthBits = 3
	noChange   = 0
)

// References to generated trie.

var trie = newCaseTrie(0)

var sparse = sparseBlocks{
	values:  sparseValues[:],
	offsets: sparseOffsets[:],
}

// Sparse block lookup code.

// valueRange is an entry in a sparse block.
type valueRange struct {
	value  uint16
	lo, hi byte
}

type sparseBlocks struct {
	values  []valueRange
	offsets []uint16
}

// lookup returns the value from values block n for byte b using binary search.
func (s *sparseBlocks) lookup(n uint32, b byte) uint16 {
	lo := s.offsets[n]
	hi := s.offsets[n+1]
	for lo < hi {
		m := lo + (hi-lo)/2
		r := s.values[m]
		if r.lo <= b && b <= r.hi {
			return r.value
		}
		if b < r.lo {
			hi = m
		} else {
			lo = m + 1
		}
	}
	return 0
}

// lastRuneForTesting is the last rune used for testing. Everything after this
// is boring.
const lastRuneForTesting = rune(0x1FFFF)