Source file src/pkg/vendor/golang.org/x/text/unicode/norm/normalize.go

     1	// Copyright 2011 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	// Note: the file data_test.go that is generated should not be checked in.
     6	//go:generate go run maketables.go triegen.go
     7	//go:generate go test -tags test
     8	
     9	// Package norm contains types and functions for normalizing Unicode strings.
    10	package norm // import "golang.org/x/text/unicode/norm"
    11	
    12	import (
    13		"unicode/utf8"
    14	
    15		"golang.org/x/text/transform"
    16	)
    17	
    18	// A Form denotes a canonical representation of Unicode code points.
    19	// The Unicode-defined normalization and equivalence forms are:
    20	//
    21	//   NFC   Unicode Normalization Form C
    22	//   NFD   Unicode Normalization Form D
    23	//   NFKC  Unicode Normalization Form KC
    24	//   NFKD  Unicode Normalization Form KD
    25	//
    26	// For a Form f, this documentation uses the notation f(x) to mean
    27	// the bytes or string x converted to the given form.
    28	// A position n in x is called a boundary if conversion to the form can
    29	// proceed independently on both sides:
    30	//   f(x) == append(f(x[0:n]), f(x[n:])...)
    31	//
    32	// References: https://unicode.org/reports/tr15/ and
    33	// https://unicode.org/notes/tn5/.
    34	type Form int
    35	
    36	const (
    37		NFC Form = iota
    38		NFD
    39		NFKC
    40		NFKD
    41	)
    42	
    43	// Bytes returns f(b). May return b if f(b) = b.
    44	func (f Form) Bytes(b []byte) []byte {
    45		src := inputBytes(b)
    46		ft := formTable[f]
    47		n, ok := ft.quickSpan(src, 0, len(b), true)
    48		if ok {
    49			return b
    50		}
    51		out := make([]byte, n, len(b))
    52		copy(out, b[0:n])
    53		rb := reorderBuffer{f: *ft, src: src, nsrc: len(b), out: out, flushF: appendFlush}
    54		return doAppendInner(&rb, n)
    55	}
    56	
    57	// String returns f(s).
    58	func (f Form) String(s string) string {
    59		src := inputString(s)
    60		ft := formTable[f]
    61		n, ok := ft.quickSpan(src, 0, len(s), true)
    62		if ok {
    63			return s
    64		}
    65		out := make([]byte, n, len(s))
    66		copy(out, s[0:n])
    67		rb := reorderBuffer{f: *ft, src: src, nsrc: len(s), out: out, flushF: appendFlush}
    68		return string(doAppendInner(&rb, n))
    69	}
    70	
    71	// IsNormal returns true if b == f(b).
    72	func (f Form) IsNormal(b []byte) bool {
    73		src := inputBytes(b)
    74		ft := formTable[f]
    75		bp, ok := ft.quickSpan(src, 0, len(b), true)
    76		if ok {
    77			return true
    78		}
    79		rb := reorderBuffer{f: *ft, src: src, nsrc: len(b)}
    80		rb.setFlusher(nil, cmpNormalBytes)
    81		for bp < len(b) {
    82			rb.out = b[bp:]
    83			if bp = decomposeSegment(&rb, bp, true); bp < 0 {
    84				return false
    85			}
    86			bp, _ = rb.f.quickSpan(rb.src, bp, len(b), true)
    87		}
    88		return true
    89	}
    90	
    91	func cmpNormalBytes(rb *reorderBuffer) bool {
    92		b := rb.out
    93		for i := 0; i < rb.nrune; i++ {
    94			info := rb.rune[i]
    95			if int(info.size) > len(b) {
    96				return false
    97			}
    98			p := info.pos
    99			pe := p + info.size
   100			for ; p < pe; p++ {
   101				if b[0] != rb.byte[p] {
   102					return false
   103				}
   104				b = b[1:]
   105			}
   106		}
   107		return true
   108	}
   109	
   110	// IsNormalString returns true if s == f(s).
   111	func (f Form) IsNormalString(s string) bool {
   112		src := inputString(s)
   113		ft := formTable[f]
   114		bp, ok := ft.quickSpan(src, 0, len(s), true)
   115		if ok {
   116			return true
   117		}
   118		rb := reorderBuffer{f: *ft, src: src, nsrc: len(s)}
   119		rb.setFlusher(nil, func(rb *reorderBuffer) bool {
   120			for i := 0; i < rb.nrune; i++ {
   121				info := rb.rune[i]
   122				if bp+int(info.size) > len(s) {
   123					return false
   124				}
   125				p := info.pos
   126				pe := p + info.size
   127				for ; p < pe; p++ {
   128					if s[bp] != rb.byte[p] {
   129						return false
   130					}
   131					bp++
   132				}
   133			}
   134			return true
   135		})
   136		for bp < len(s) {
   137			if bp = decomposeSegment(&rb, bp, true); bp < 0 {
   138				return false
   139			}
   140			bp, _ = rb.f.quickSpan(rb.src, bp, len(s), true)
   141		}
   142		return true
   143	}
   144	
   145	// patchTail fixes a case where a rune may be incorrectly normalized
   146	// if it is followed by illegal continuation bytes. It returns the
   147	// patched buffer and whether the decomposition is still in progress.
   148	func patchTail(rb *reorderBuffer) bool {
   149		info, p := lastRuneStart(&rb.f, rb.out)
   150		if p == -1 || info.size == 0 {
   151			return true
   152		}
   153		end := p + int(info.size)
   154		extra := len(rb.out) - end
   155		if extra > 0 {
   156			// Potentially allocating memory. However, this only
   157			// happens with ill-formed UTF-8.
   158			x := make([]byte, 0)
   159			x = append(x, rb.out[len(rb.out)-extra:]...)
   160			rb.out = rb.out[:end]
   161			decomposeToLastBoundary(rb)
   162			rb.doFlush()
   163			rb.out = append(rb.out, x...)
   164			return false
   165		}
   166		buf := rb.out[p:]
   167		rb.out = rb.out[:p]
   168		decomposeToLastBoundary(rb)
   169		if s := rb.ss.next(info); s == ssStarter {
   170			rb.doFlush()
   171			rb.ss.first(info)
   172		} else if s == ssOverflow {
   173			rb.doFlush()
   174			rb.insertCGJ()
   175			rb.ss = 0
   176		}
   177		rb.insertUnsafe(inputBytes(buf), 0, info)
   178		return true
   179	}
   180	
   181	func appendQuick(rb *reorderBuffer, i int) int {
   182		if rb.nsrc == i {
   183			return i
   184		}
   185		end, _ := rb.f.quickSpan(rb.src, i, rb.nsrc, true)
   186		rb.out = rb.src.appendSlice(rb.out, i, end)
   187		return end
   188	}
   189	
   190	// Append returns f(append(out, b...)).
   191	// The buffer out must be nil, empty, or equal to f(out).
   192	func (f Form) Append(out []byte, src ...byte) []byte {
   193		return f.doAppend(out, inputBytes(src), len(src))
   194	}
   195	
   196	func (f Form) doAppend(out []byte, src input, n int) []byte {
   197		if n == 0 {
   198			return out
   199		}
   200		ft := formTable[f]
   201		// Attempt to do a quickSpan first so we can avoid initializing the reorderBuffer.
   202		if len(out) == 0 {
   203			p, _ := ft.quickSpan(src, 0, n, true)
   204			out = src.appendSlice(out, 0, p)
   205			if p == n {
   206				return out
   207			}
   208			rb := reorderBuffer{f: *ft, src: src, nsrc: n, out: out, flushF: appendFlush}
   209			return doAppendInner(&rb, p)
   210		}
   211		rb := reorderBuffer{f: *ft, src: src, nsrc: n}
   212		return doAppend(&rb, out, 0)
   213	}
   214	
   215	func doAppend(rb *reorderBuffer, out []byte, p int) []byte {
   216		rb.setFlusher(out, appendFlush)
   217		src, n := rb.src, rb.nsrc
   218		doMerge := len(out) > 0
   219		if q := src.skipContinuationBytes(p); q > p {
   220			// Move leading non-starters to destination.
   221			rb.out = src.appendSlice(rb.out, p, q)
   222			p = q
   223			doMerge = patchTail(rb)
   224		}
   225		fd := &rb.f
   226		if doMerge {
   227			var info Properties
   228			if p < n {
   229				info = fd.info(src, p)
   230				if !info.BoundaryBefore() || info.nLeadingNonStarters() > 0 {
   231					if p == 0 {
   232						decomposeToLastBoundary(rb)
   233					}
   234					p = decomposeSegment(rb, p, true)
   235				}
   236			}
   237			if info.size == 0 {
   238				rb.doFlush()
   239				// Append incomplete UTF-8 encoding.
   240				return src.appendSlice(rb.out, p, n)
   241			}
   242			if rb.nrune > 0 {
   243				return doAppendInner(rb, p)
   244			}
   245		}
   246		p = appendQuick(rb, p)
   247		return doAppendInner(rb, p)
   248	}
   249	
   250	func doAppendInner(rb *reorderBuffer, p int) []byte {
   251		for n := rb.nsrc; p < n; {
   252			p = decomposeSegment(rb, p, true)
   253			p = appendQuick(rb, p)
   254		}
   255		return rb.out
   256	}
   257	
   258	// AppendString returns f(append(out, []byte(s))).
   259	// The buffer out must be nil, empty, or equal to f(out).
   260	func (f Form) AppendString(out []byte, src string) []byte {
   261		return f.doAppend(out, inputString(src), len(src))
   262	}
   263	
   264	// QuickSpan returns a boundary n such that b[0:n] == f(b[0:n]).
   265	// It is not guaranteed to return the largest such n.
   266	func (f Form) QuickSpan(b []byte) int {
   267		n, _ := formTable[f].quickSpan(inputBytes(b), 0, len(b), true)
   268		return n
   269	}
   270	
   271	// Span implements transform.SpanningTransformer. It returns a boundary n such
   272	// that b[0:n] == f(b[0:n]). It is not guaranteed to return the largest such n.
   273	func (f Form) Span(b []byte, atEOF bool) (n int, err error) {
   274		n, ok := formTable[f].quickSpan(inputBytes(b), 0, len(b), atEOF)
   275		if n < len(b) {
   276			if !ok {
   277				err = transform.ErrEndOfSpan
   278			} else {
   279				err = transform.ErrShortSrc
   280			}
   281		}
   282		return n, err
   283	}
   284	
   285	// SpanString returns a boundary n such that s[0:n] == f(s[0:n]).
   286	// It is not guaranteed to return the largest such n.
   287	func (f Form) SpanString(s string, atEOF bool) (n int, err error) {
   288		n, ok := formTable[f].quickSpan(inputString(s), 0, len(s), atEOF)
   289		if n < len(s) {
   290			if !ok {
   291				err = transform.ErrEndOfSpan
   292			} else {
   293				err = transform.ErrShortSrc
   294			}
   295		}
   296		return n, err
   297	}
   298	
   299	// quickSpan returns a boundary n such that src[0:n] == f(src[0:n]) and
   300	// whether any non-normalized parts were found. If atEOF is false, n will
   301	// not point past the last segment if this segment might be become
   302	// non-normalized by appending other runes.
   303	func (f *formInfo) quickSpan(src input, i, end int, atEOF bool) (n int, ok bool) {
   304		var lastCC uint8
   305		ss := streamSafe(0)
   306		lastSegStart := i
   307		for n = end; i < n; {
   308			if j := src.skipASCII(i, n); i != j {
   309				i = j
   310				lastSegStart = i - 1
   311				lastCC = 0
   312				ss = 0
   313				continue
   314			}
   315			info := f.info(src, i)
   316			if info.size == 0 {
   317				if atEOF {
   318					// include incomplete runes
   319					return n, true
   320				}
   321				return lastSegStart, true
   322			}
   323			// This block needs to be before the next, because it is possible to
   324			// have an overflow for runes that are starters (e.g. with U+FF9E).
   325			switch ss.next(info) {
   326			case ssStarter:
   327				lastSegStart = i
   328			case ssOverflow:
   329				return lastSegStart, false
   330			case ssSuccess:
   331				if lastCC > info.ccc {
   332					return lastSegStart, false
   333				}
   334			}
   335			if f.composing {
   336				if !info.isYesC() {
   337					break
   338				}
   339			} else {
   340				if !info.isYesD() {
   341					break
   342				}
   343			}
   344			lastCC = info.ccc
   345			i += int(info.size)
   346		}
   347		if i == n {
   348			if !atEOF {
   349				n = lastSegStart
   350			}
   351			return n, true
   352		}
   353		return lastSegStart, false
   354	}
   355	
   356	// QuickSpanString returns a boundary n such that s[0:n] == f(s[0:n]).
   357	// It is not guaranteed to return the largest such n.
   358	func (f Form) QuickSpanString(s string) int {
   359		n, _ := formTable[f].quickSpan(inputString(s), 0, len(s), true)
   360		return n
   361	}
   362	
   363	// FirstBoundary returns the position i of the first boundary in b
   364	// or -1 if b contains no boundary.
   365	func (f Form) FirstBoundary(b []byte) int {
   366		return f.firstBoundary(inputBytes(b), len(b))
   367	}
   368	
   369	func (f Form) firstBoundary(src input, nsrc int) int {
   370		i := src.skipContinuationBytes(0)
   371		if i >= nsrc {
   372			return -1
   373		}
   374		fd := formTable[f]
   375		ss := streamSafe(0)
   376		// We should call ss.first here, but we can't as the first rune is
   377		// skipped already. This means FirstBoundary can't really determine
   378		// CGJ insertion points correctly. Luckily it doesn't have to.
   379		for {
   380			info := fd.info(src, i)
   381			if info.size == 0 {
   382				return -1
   383			}
   384			if s := ss.next(info); s != ssSuccess {
   385				return i
   386			}
   387			i += int(info.size)
   388			if i >= nsrc {
   389				if !info.BoundaryAfter() && !ss.isMax() {
   390					return -1
   391				}
   392				return nsrc
   393			}
   394		}
   395	}
   396	
   397	// FirstBoundaryInString returns the position i of the first boundary in s
   398	// or -1 if s contains no boundary.
   399	func (f Form) FirstBoundaryInString(s string) int {
   400		return f.firstBoundary(inputString(s), len(s))
   401	}
   402	
   403	// NextBoundary reports the index of the boundary between the first and next
   404	// segment in b or -1 if atEOF is false and there are not enough bytes to
   405	// determine this boundary.
   406	func (f Form) NextBoundary(b []byte, atEOF bool) int {
   407		return f.nextBoundary(inputBytes(b), len(b), atEOF)
   408	}
   409	
   410	// NextBoundaryInString reports the index of the boundary between the first and
   411	// next segment in b or -1 if atEOF is false and there are not enough bytes to
   412	// determine this boundary.
   413	func (f Form) NextBoundaryInString(s string, atEOF bool) int {
   414		return f.nextBoundary(inputString(s), len(s), atEOF)
   415	}
   416	
   417	func (f Form) nextBoundary(src input, nsrc int, atEOF bool) int {
   418		if nsrc == 0 {
   419			if atEOF {
   420				return 0
   421			}
   422			return -1
   423		}
   424		fd := formTable[f]
   425		info := fd.info(src, 0)
   426		if info.size == 0 {
   427			if atEOF {
   428				return 1
   429			}
   430			return -1
   431		}
   432		ss := streamSafe(0)
   433		ss.first(info)
   434	
   435		for i := int(info.size); i < nsrc; i += int(info.size) {
   436			info = fd.info(src, i)
   437			if info.size == 0 {
   438				if atEOF {
   439					return i
   440				}
   441				return -1
   442			}
   443			// TODO: Using streamSafe to determine the boundary isn't the same as
   444			// using BoundaryBefore. Determine which should be used.
   445			if s := ss.next(info); s != ssSuccess {
   446				return i
   447			}
   448		}
   449		if !atEOF && !info.BoundaryAfter() && !ss.isMax() {
   450			return -1
   451		}
   452		return nsrc
   453	}
   454	
   455	// LastBoundary returns the position i of the last boundary in b
   456	// or -1 if b contains no boundary.
   457	func (f Form) LastBoundary(b []byte) int {
   458		return lastBoundary(formTable[f], b)
   459	}
   460	
   461	func lastBoundary(fd *formInfo, b []byte) int {
   462		i := len(b)
   463		info, p := lastRuneStart(fd, b)
   464		if p == -1 {
   465			return -1
   466		}
   467		if info.size == 0 { // ends with incomplete rune
   468			if p == 0 { // starts with incomplete rune
   469				return -1
   470			}
   471			i = p
   472			info, p = lastRuneStart(fd, b[:i])
   473			if p == -1 { // incomplete UTF-8 encoding or non-starter bytes without a starter
   474				return i
   475			}
   476		}
   477		if p+int(info.size) != i { // trailing non-starter bytes: illegal UTF-8
   478			return i
   479		}
   480		if info.BoundaryAfter() {
   481			return i
   482		}
   483		ss := streamSafe(0)
   484		v := ss.backwards(info)
   485		for i = p; i >= 0 && v != ssStarter; i = p {
   486			info, p = lastRuneStart(fd, b[:i])
   487			if v = ss.backwards(info); v == ssOverflow {
   488				break
   489			}
   490			if p+int(info.size) != i {
   491				if p == -1 { // no boundary found
   492					return -1
   493				}
   494				return i // boundary after an illegal UTF-8 encoding
   495			}
   496		}
   497		return i
   498	}
   499	
   500	// decomposeSegment scans the first segment in src into rb. It inserts 0x034f
   501	// (Grapheme Joiner) when it encounters a sequence of more than 30 non-starters
   502	// and returns the number of bytes consumed from src or iShortDst or iShortSrc.
   503	func decomposeSegment(rb *reorderBuffer, sp int, atEOF bool) int {
   504		// Force one character to be consumed.
   505		info := rb.f.info(rb.src, sp)
   506		if info.size == 0 {
   507			return 0
   508		}
   509		if s := rb.ss.next(info); s == ssStarter {
   510			// TODO: this could be removed if we don't support merging.
   511			if rb.nrune > 0 {
   512				goto end
   513			}
   514		} else if s == ssOverflow {
   515			rb.insertCGJ()
   516			goto end
   517		}
   518		if err := rb.insertFlush(rb.src, sp, info); err != iSuccess {
   519			return int(err)
   520		}
   521		for {
   522			sp += int(info.size)
   523			if sp >= rb.nsrc {
   524				if !atEOF && !info.BoundaryAfter() {
   525					return int(iShortSrc)
   526				}
   527				break
   528			}
   529			info = rb.f.info(rb.src, sp)
   530			if info.size == 0 {
   531				if !atEOF {
   532					return int(iShortSrc)
   533				}
   534				break
   535			}
   536			if s := rb.ss.next(info); s == ssStarter {
   537				break
   538			} else if s == ssOverflow {
   539				rb.insertCGJ()
   540				break
   541			}
   542			if err := rb.insertFlush(rb.src, sp, info); err != iSuccess {
   543				return int(err)
   544			}
   545		}
   546	end:
   547		if !rb.doFlush() {
   548			return int(iShortDst)
   549		}
   550		return sp
   551	}
   552	
   553	// lastRuneStart returns the runeInfo and position of the last
   554	// rune in buf or the zero runeInfo and -1 if no rune was found.
   555	func lastRuneStart(fd *formInfo, buf []byte) (Properties, int) {
   556		p := len(buf) - 1
   557		for ; p >= 0 && !utf8.RuneStart(buf[p]); p-- {
   558		}
   559		if p < 0 {
   560			return Properties{}, -1
   561		}
   562		return fd.info(inputBytes(buf), p), p
   563	}
   564	
   565	// decomposeToLastBoundary finds an open segment at the end of the buffer
   566	// and scans it into rb. Returns the buffer minus the last segment.
   567	func decomposeToLastBoundary(rb *reorderBuffer) {
   568		fd := &rb.f
   569		info, i := lastRuneStart(fd, rb.out)
   570		if int(info.size) != len(rb.out)-i {
   571			// illegal trailing continuation bytes
   572			return
   573		}
   574		if info.BoundaryAfter() {
   575			return
   576		}
   577		var add [maxNonStarters + 1]Properties // stores runeInfo in reverse order
   578		padd := 0
   579		ss := streamSafe(0)
   580		p := len(rb.out)
   581		for {
   582			add[padd] = info
   583			v := ss.backwards(info)
   584			if v == ssOverflow {
   585				// Note that if we have an overflow, it the string we are appending to
   586				// is not correctly normalized. In this case the behavior is undefined.
   587				break
   588			}
   589			padd++
   590			p -= int(info.size)
   591			if v == ssStarter || p < 0 {
   592				break
   593			}
   594			info, i = lastRuneStart(fd, rb.out[:p])
   595			if int(info.size) != p-i {
   596				break
   597			}
   598		}
   599		rb.ss = ss
   600		// Copy bytes for insertion as we may need to overwrite rb.out.
   601		var buf [maxBufferSize * utf8.UTFMax]byte
   602		cp := buf[:copy(buf[:], rb.out[p:])]
   603		rb.out = rb.out[:p]
   604		for padd--; padd >= 0; padd-- {
   605			info = add[padd]
   606			rb.insertUnsafe(inputBytes(cp), 0, info)
   607			cp = cp[info.size:]
   608		}
   609	}
   610	

View as plain text