Debian Codegraph @

pkg/cel/escaping.go

raw
1 /*
2 Copyright 2021 The Kubernetes Authors.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 package cel
18
19 import (
20 "regexp"
21
22 "k8s.io/apimachinery/pkg/util/sets"
23 )
24
25 // celReservedSymbols is a list of RESERVED symbols defined in the CEL lexer.
26 // No identifiers are allowed to collide with these symbols.
27 // https://github.com/google/cel-spec/blob/master/doc/langdef.md#syntax
28 var celReservedSymbols = sets.NewString(
29 "true", "false", "null", "in",
30 "as", "break", "const", "continue", "else",
31 "for", "function", "if", "import", "let",
32 "loop", "package", "namespace", "return", // !! 'namespace' is used heavily in Kubernetes
33 "var", "void", "while",
34 )
35
36 // expandMatcher matches the escape sequence, characters that are escaped, and characters that are unsupported
37 var expandMatcher = regexp.MustCompile(`(__|[-./]|[^a-zA-Z0-9-./_])`)
38
39 // newCharacterFilter returns a boolean array to indicate the allowed characters
40 func newCharacterFilter(characters string) []bool {
41 maxChar := 0
42 for _, c := range characters {
43 if maxChar < int(c) {
44 maxChar = int(c)
45 }
46 }
47 filter := make([]bool, maxChar+1)
48
49 for _, c := range characters {
50 filter[int(c)] = true
51 }
52
53 return filter
54 }
55
56 type escapeCheck struct {
57 canSkipRegex bool
58 invalidCharFound bool
59 }
60
61 // skipRegexCheck checks if escape would be skipped.
62 // if invalidCharFound is true, it must have invalid character; if invalidCharFound is false, not sure if it has invalid character or not
63 func skipRegexCheck(ident string) escapeCheck {
64 escapeCheck := escapeCheck{canSkipRegex: true, invalidCharFound: false}
65 // skip escape if possible
66 previous_underscore := false
67 for _, c := range ident {
68 if c == '/' || c == '-' || c == '.' {
69 escapeCheck.canSkipRegex = false
70 return escapeCheck
71 }
72 intc := int(c)
73 if intc < 0 || intc >= len(validCharacterFilter) || !validCharacterFilter[intc] {
74 escapeCheck.invalidCharFound = true
75 return escapeCheck
76 }
77 if c == '_' && previous_underscore {
78 escapeCheck.canSkipRegex = false
79 return escapeCheck
80 }
81
82 previous_underscore = c == '_'
83 }
84 return escapeCheck
85 }
86
87 // validCharacterFilter indicates the allowed characters.
88 var validCharacterFilter = newCharacterFilter("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_")
89
90 // Escape escapes ident and returns a CEL identifier (of the form '[a-zA-Z_][a-zA-Z0-9_]*'), or returns
91 // false if the ident does not match the supported input format of `[a-zA-Z_.-/][a-zA-Z0-9_.-/]*`.
92 // Escaping Rules:
93 // - '__' escapes to '__underscores__'
94 // - '.' escapes to '__dot__'
95 // - '-' escapes to '__dash__'
96 // - '/' escapes to '__slash__'
97 // - Identifiers that exactly match a CEL RESERVED keyword escape to '__{keyword}__'. The keywords are: "true", "false",
98 // "null", "in", "as", "break", "const", "continue", "else", "for", "function", "if", "import", "let", loop", "package",
99 // "namespace", "return".
100 func Escape(ident string) (string, bool) {
101 if len(ident) == 0 || ('0' <= ident[0] && ident[0] <= '9') {
102 return "", false
103 }
104 if celReservedSymbols.Has(ident) {
105 return "__" + ident + "__", true
106 }
107
108 escapeCheck := skipRegexCheck(ident)
109 if escapeCheck.invalidCharFound {
110 return "", false
111 }
112 if escapeCheck.canSkipRegex {
113 return ident, true
114 }
115
116 ok := true
117 ident = expandMatcher.ReplaceAllStringFunc(ident, func(s string) string {
118 switch s {
119 case "__":
120 return "__underscores__"
121 case ".":
122 return "__dot__"
123 case "-":
124 return "__dash__"
125 case "/":
126 return "__slash__"
127 default: // matched a unsupported supported
128 ok = false
129 return ""
130 }
131 })
132 if !ok {
133 return "", false
134 }
135 return ident, true
136 }
137
138 var unexpandMatcher = regexp.MustCompile(`(_{2}[^_]+_{2})`)
139
140 // Unescape unescapes an CEL identifier containing the escape sequences described in Escape, or return false if the
141 // string contains invalid escape sequences. The escaped input is expected to be a valid CEL identifier, but is
142 // not checked.
143 func Unescape(escaped string) (string, bool) {
144 ok := true
145 escaped = unexpandMatcher.ReplaceAllStringFunc(escaped, func(s string) string {
146 contents := s[2 : len(s)-2]
147 switch contents {
148 case "underscores":
149 return "__"
150 case "dot":
151 return "."
152 case "dash":
153 return "-"
154 case "slash":
155 return "/"
156 }
157 if celReservedSymbols.Has(contents) {
158 if len(s) != len(escaped) {
159 ok = false
160 }
161 return contents
162 }
163 ok = false
164 return ""
165 })
166 if !ok {
167 return "", false
168 }
169 return escaped, true
170 }