match.go

Documentation: cuelang.org/go/pkg/path

     1  // Copyright 2020 CUE Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  // Copyright 2010 The Go Authors. All rights reserved.
    16  // Use of this source code is governed by a BSD-style
    17  // license that can be found in the LICENSE file.
    18  
    19  package path
    20  
    21  import (
    22  	"errors"
    23  	"strings"
    24  	"unicode/utf8"
    25  )
    26  
    27  // ErrBadPattern indicates a pattern was malformed.
    28  var ErrBadPattern = errors.New("syntax error in pattern")
    29  
    30  // Match reports whether name matches the shell file name pattern.
    31  // The pattern syntax is:
    32  //
    33  //	pattern:
    34  //		{ term }
    35  //	term:
    36  //		'*'         matches any sequence of non-Separator characters
    37  //		'?'         matches any single non-Separator character
    38  //		'[' [ '^' ] { character-range } ']'
    39  //		            character class (must be non-empty)
    40  //		c           matches character c (c != '*', '?', '\\', '[')
    41  //		'\\' c      matches character c
    42  //
    43  //	character-range:
    44  //		c           matches character c (c != '\\', '-', ']')
    45  //		'\\' c      matches character c
    46  //		lo '-' hi   matches character c for lo <= c <= hi
    47  //
    48  // Match requires pattern to match all of name, not just a substring.
    49  // The only possible returned error is ErrBadPattern, when pattern
    50  // is malformed.
    51  //
    52  // On Windows, escaping is disabled. Instead, '\\' is treated as
    53  // path separator.
    54  func Match(pattern, name string, o OS) (matched bool, err error) {
    55  	os := getOS(o)
    56  Pattern:
    57  	for len(pattern) > 0 {
    58  		var star bool
    59  		var chunk string
    60  		star, chunk, pattern = scanChunk(pattern, os)
    61  		if star && chunk == "" {
    62  			// Trailing * matches rest of string unless it has a /.
    63  			return !strings.Contains(name, string(os.Separator)), nil
    64  		}
    65  		// Look for match at current position.
    66  		t, ok, err := matchChunk(chunk, name, os)
    67  		// if we're the last chunk, make sure we've exhausted the name
    68  		// otherwise we'll give a false result even if we could still match
    69  		// using the star
    70  		if ok && (len(t) == 0 || len(pattern) > 0) {
    71  			name = t
    72  			continue
    73  		}
    74  		if err != nil {
    75  			return false, err
    76  		}
    77  		if star {
    78  			// Look for match skipping i+1 bytes.
    79  			// Cannot skip /.
    80  			for i := 0; i < len(name) && name[i] != os.Separator; i++ {
    81  				t, ok, err := matchChunk(chunk, name[i+1:], os)
    82  				if ok {
    83  					// if we're the last chunk, make sure we exhausted the name
    84  					if len(pattern) == 0 && len(t) > 0 {
    85  						continue
    86  					}
    87  					name = t
    88  					continue Pattern
    89  				}
    90  				if err != nil {
    91  					return false, err
    92  				}
    93  			}
    94  		}
    95  		return false, nil
    96  	}
    97  	return len(name) == 0, nil
    98  }
    99  
   100  // scanChunk gets the next segment of pattern, which is a non-star string
   101  // possibly preceded by a star.
   102  func scanChunk(pattern string, os os) (star bool, chunk, rest string) {
   103  	for len(pattern) > 0 && pattern[0] == '*' {
   104  		pattern = pattern[1:]
   105  		star = true
   106  	}
   107  	inrange := false
   108  	var i int
   109  Scan:
   110  	for i = 0; i < len(pattern); i++ {
   111  		switch pattern[i] {
   112  		case '\\':
   113  			if !os.isWindows() {
   114  				// error check handled in matchChunk: bad pattern.
   115  				if i+1 < len(pattern) {
   116  					i++
   117  				}
   118  			}
   119  		case '[':
   120  			inrange = true
   121  		case ']':
   122  			inrange = false
   123  		case '*':
   124  			if !inrange {
   125  				break Scan
   126  			}
   127  		}
   128  	}
   129  	return star, pattern[0:i], pattern[i:]
   130  }
   131  
   132  // matchChunk checks whether chunk matches the beginning of s.
   133  // If so, it returns the remainder of s (after the match).
   134  // Chunk is all single-character operators: literals, char classes, and ?.
   135  func matchChunk(chunk, s string, os os) (rest string, ok bool, err error) {
   136  	// failed records whether the match has failed.
   137  	// After the match fails, the loop continues on processing chunk,
   138  	// checking that the pattern is well-formed but no longer reading s.
   139  	failed := false
   140  	for len(chunk) > 0 {
   141  		if !failed && len(s) == 0 {
   142  			failed = true
   143  		}
   144  		switch chunk[0] {
   145  		case '[':
   146  			// character class
   147  			var r rune
   148  			if !failed {
   149  				var n int
   150  				r, n = utf8.DecodeRuneInString(s)
   151  				s = s[n:]
   152  			}
   153  			chunk = chunk[1:]
   154  			// possibly negated
   155  			negated := false
   156  			if len(chunk) > 0 && chunk[0] == '^' {
   157  				negated = true
   158  				chunk = chunk[1:]
   159  			}
   160  			// parse all ranges
   161  			match := false
   162  			nrange := 0
   163  			for {
   164  				if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
   165  					chunk = chunk[1:]
   166  					break
   167  				}
   168  				var lo, hi rune
   169  				if lo, chunk, err = getEsc(chunk, os); err != nil {
   170  					return "", false, err
   171  				}
   172  				hi = lo
   173  				if chunk[0] == '-' {
   174  					if hi, chunk, err = getEsc(chunk[1:], os); err != nil {
   175  						return "", false, err
   176  					}
   177  				}
   178  				if lo <= r && r <= hi {
   179  					match = true
   180  				}
   181  				nrange++
   182  			}
   183  			if match == negated {
   184  				failed = true
   185  			}
   186  
   187  		case '?':
   188  			if !failed {
   189  				if s[0] == os.Separator {
   190  					failed = true
   191  				}
   192  				_, n := utf8.DecodeRuneInString(s)
   193  				s = s[n:]
   194  			}
   195  			chunk = chunk[1:]
   196  
   197  		case '\\':
   198  			if !os.isWindows() {
   199  				chunk = chunk[1:]
   200  				if len(chunk) == 0 {
   201  					return "", false, ErrBadPattern
   202  				}
   203  			}
   204  			fallthrough
   205  
   206  		default:
   207  			if !failed {
   208  				if chunk[0] != s[0] {
   209  					failed = true
   210  				}
   211  				s = s[1:]
   212  			}
   213  			chunk = chunk[1:]
   214  		}
   215  	}
   216  	if failed {
   217  		return "", false, nil
   218  	}
   219  	return s, true, nil
   220  }
   221  
   222  // getEsc gets a possibly-escaped character from chunk, for a character class.
   223  func getEsc(chunk string, os os) (r rune, nchunk string, err error) {
   224  	if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
   225  		err = ErrBadPattern
   226  		return
   227  	}
   228  	if chunk[0] == '\\' && !os.isWindows() {
   229  		chunk = chunk[1:]
   230  		if len(chunk) == 0 {
   231  			err = ErrBadPattern
   232  			return
   233  		}
   234  	}
   235  	r, n := utf8.DecodeRuneInString(chunk)
   236  	if r == utf8.RuneError && n == 1 {
   237  		err = ErrBadPattern
   238  	}
   239  	nchunk = chunk[n:]
   240  	if len(nchunk) == 0 {
   241  		err = ErrBadPattern
   242  	}
   243  	return
   244  }
   245
View as plain text