| 1 | #!/usr/bin/env python2
|
| 2 | # Copyright 2016 Andy Chu. All rights reserved.
|
| 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 | bool_parse.py - Parse boolean expressions.
|
| 10 |
|
| 11 | In contrast to test / [, the parsing of [[ expressions is done BEFORE
|
| 12 | evaluation. So we are parsing a list of Word instances to an AST, rather than
|
| 13 | a list of strings.
|
| 14 |
|
| 15 | Grammar from http://compilers.iecc.com/crenshaw/tutor6.txt, adapted to ANTLR
|
| 16 | syntax.
|
| 17 |
|
| 18 | Expr : Term (OR Term)*
|
| 19 | Term : Negated (AND Negated)*
|
| 20 | Negated : '!'? Factor
|
| 21 | Factor : WORD
|
| 22 | | UNARY_OP WORD
|
| 23 | | WORD BINARY_OP WORD
|
| 24 | | '(' Expr ')'
|
| 25 |
|
| 26 | OR = || -o
|
| 27 | AND = && -a
|
| 28 | WORD = any word
|
| 29 | UNARY_OP: -z -n, etc.
|
| 30 | BINARY_OP: -gt, -ot, ==, etc.
|
| 31 | """
|
| 32 |
|
| 33 | from _devbuild.gen.id_kind_asdl import Id, Kind
|
| 34 | from _devbuild.gen.types_asdl import lex_mode_t, lex_mode_e
|
| 35 | from _devbuild.gen.syntax_asdl import (loc, word_t, word_e, bool_expr,
|
| 36 | bool_expr_t, Token)
|
| 37 | from core import ui
|
| 38 | from core.error import p_die
|
| 39 | from frontend import consts
|
| 40 | from mycpp.mylib import log
|
| 41 | from osh import word_
|
| 42 |
|
| 43 | from typing import List, Optional, Tuple, TYPE_CHECKING
|
| 44 | if TYPE_CHECKING:
|
| 45 | from osh.word_parse import WordEmitter
|
| 46 |
|
| 47 | # import libc # for regex_parse
|
| 48 |
|
| 49 | _ = log
|
| 50 |
|
| 51 |
|
| 52 | class BoolParser(object):
|
| 53 | """Parses [[ at compile time and [ at runtime."""
|
| 54 |
|
| 55 | def __init__(self, w_parser):
|
| 56 | # type: (WordEmitter) -> None
|
| 57 | self.w_parser = w_parser
|
| 58 | # Either one word or two words for lookahead
|
| 59 | self.words = [] # type: List[word_t]
|
| 60 |
|
| 61 | self.cur_word = None # type: Optional[word_t]
|
| 62 | self.bool_id = Id.Undefined_Tok
|
| 63 | self.bool_kind = Kind.Undefined
|
| 64 |
|
| 65 | def _NextOne(self, lex_mode=lex_mode_e.DBracket):
|
| 66 | # type: (lex_mode_t) -> None
|
| 67 | n = len(self.words)
|
| 68 | if n == 2:
|
| 69 | assert lex_mode == lex_mode_e.DBracket
|
| 70 | self.words[0] = self.words[1]
|
| 71 | self.cur_word = self.words[0]
|
| 72 | self.words.pop()
|
| 73 | elif n in (0, 1):
|
| 74 | w = self.w_parser.ReadWord(lex_mode) # may raise
|
| 75 | if n == 0:
|
| 76 | self.words.append(w)
|
| 77 | else:
|
| 78 | self.words[0] = w
|
| 79 | self.cur_word = w
|
| 80 |
|
| 81 | assert self.cur_word is not None
|
| 82 | self.bool_id = word_.BoolId(self.cur_word)
|
| 83 | self.bool_kind = consts.GetKind(self.bool_id)
|
| 84 | #log('--- word %s', self.cur_word)
|
| 85 | #log('bool_id %s %s %s', Id_str(self.bool_id), Kind_str(self.bool_kind), lex_mode)
|
| 86 |
|
| 87 | def _Next(self, lex_mode=lex_mode_e.DBracket):
|
| 88 | # type: (lex_mode_t) -> None
|
| 89 | """Advance to the next token, skipping newlines.
|
| 90 |
|
| 91 | We don't handle newlines in the lexer because we want the
|
| 92 | newline after ]] to be Id.Op_Newline rather than Id.WS_Newline.
|
| 93 | It's more complicated if it's Id.WS_Newline -- we might have to
|
| 94 | unread tokens, etc.
|
| 95 | """
|
| 96 | while True:
|
| 97 | self._NextOne(lex_mode=lex_mode)
|
| 98 | if self.bool_id != Id.Op_Newline:
|
| 99 | break
|
| 100 |
|
| 101 | def _LookAhead(self):
|
| 102 | # type: () -> word_t
|
| 103 | n = len(self.words)
|
| 104 | if n != 1:
|
| 105 | raise AssertionError(n)
|
| 106 |
|
| 107 | w = self.w_parser.ReadWord(lex_mode_e.DBracket) # may raise
|
| 108 | self.words.append(w) # Save it for _Next()
|
| 109 | return w
|
| 110 |
|
| 111 | def Parse(self):
|
| 112 | # type: () -> Tuple[bool_expr_t, Token]
|
| 113 | self._Next()
|
| 114 |
|
| 115 | node = self.ParseExpr()
|
| 116 | if self.bool_id != Id.Lit_DRightBracket:
|
| 117 | #p_die("Expected ]], got %r", self.cur_word, word=self.cur_word)
|
| 118 | # NOTE: This might be better as unexpected token, since ]] doesn't always
|
| 119 | # make sense.
|
| 120 | p_die('Expected ]]', loc.Word(self.cur_word))
|
| 121 |
|
| 122 | # Extract the ']]' keyword and return it's token for location tracking
|
| 123 | right = word_.LiteralToken(self.cur_word)
|
| 124 | assert right is not None
|
| 125 |
|
| 126 | return node, right
|
| 127 |
|
| 128 | def _TestAtEnd(self):
|
| 129 | # type: () -> bool
|
| 130 | """For unit tests only."""
|
| 131 | return self.bool_id == Id.Lit_DRightBracket
|
| 132 |
|
| 133 | def ParseForBuiltin(self):
|
| 134 | # type: () -> bool_expr_t
|
| 135 | """For test builtin."""
|
| 136 | self._Next()
|
| 137 |
|
| 138 | node = self.ParseExpr()
|
| 139 | if self.bool_id != Id.Eof_Real:
|
| 140 | p_die('Unexpected trailing word %s' % word_.Pretty(self.cur_word),
|
| 141 | loc.Word(self.cur_word))
|
| 142 |
|
| 143 | return node
|
| 144 |
|
| 145 | def ParseExpr(self):
|
| 146 | # type: () -> bool_expr_t
|
| 147 | """
|
| 148 | Iterative:
|
| 149 | Expr : Term (OR Term)*
|
| 150 |
|
| 151 | Right recursion:
|
| 152 | Expr : Term (OR Expr)?
|
| 153 | """
|
| 154 | left = self.ParseTerm()
|
| 155 | # [[ uses || but [ uses -o
|
| 156 | if self.bool_id in (Id.Op_DPipe, Id.BoolUnary_o):
|
| 157 | self._Next()
|
| 158 | right = self.ParseExpr()
|
| 159 | return bool_expr.LogicalOr(left, right)
|
| 160 | else:
|
| 161 | return left
|
| 162 |
|
| 163 | def ParseTerm(self):
|
| 164 | # type: () -> bool_expr_t
|
| 165 | """
|
| 166 | Term : Negated (AND Negated)*
|
| 167 |
|
| 168 | Right recursion:
|
| 169 | Term : Negated (AND Term)?
|
| 170 | """
|
| 171 | left = self.ParseNegatedFactor()
|
| 172 | # [[ uses && but [ uses -a
|
| 173 | if self.bool_id in (Id.Op_DAmp, Id.BoolUnary_a):
|
| 174 | self._Next()
|
| 175 | right = self.ParseTerm()
|
| 176 | return bool_expr.LogicalAnd(left, right)
|
| 177 | else:
|
| 178 | return left
|
| 179 |
|
| 180 | def ParseNegatedFactor(self):
|
| 181 | # type: () -> bool_expr_t
|
| 182 | """
|
| 183 | Negated : '!'? Factor
|
| 184 | """
|
| 185 | if self.bool_id == Id.KW_Bang:
|
| 186 | self._Next()
|
| 187 | child = self.ParseFactor()
|
| 188 | return bool_expr.LogicalNot(child)
|
| 189 | else:
|
| 190 | return self.ParseFactor()
|
| 191 |
|
| 192 | def ParseFactor(self):
|
| 193 | # type: () -> bool_expr_t
|
| 194 | """
|
| 195 | Factor : WORD
|
| 196 | | UNARY_OP WORD
|
| 197 | | WORD =~ Regex
|
| 198 | | WORD BINARY_OP WORD
|
| 199 | | '(' Expr ')'
|
| 200 | """
|
| 201 | if self.bool_kind == Kind.BoolUnary:
|
| 202 | # Just save the type and not the token itself?
|
| 203 | op = self.bool_id
|
| 204 | self._Next()
|
| 205 | w = self.cur_word
|
| 206 | # e.g. [[ -f < ]]. But [[ -f '<' ]] is OK
|
| 207 |
|
| 208 | tag = w.tag()
|
| 209 | if tag != word_e.Compound and tag != word_e.String:
|
| 210 | p_die('Invalid argument to unary operator', loc.Word(w))
|
| 211 | self._Next()
|
| 212 |
|
| 213 | tilde = word_.TildeDetect(w)
|
| 214 | if tilde:
|
| 215 | w = tilde
|
| 216 |
|
| 217 | node = bool_expr.Unary(op, w) # type: bool_expr_t
|
| 218 | return node
|
| 219 |
|
| 220 | if self.bool_kind == Kind.Word:
|
| 221 | # Peek ahead another token.
|
| 222 | t2 = self._LookAhead()
|
| 223 | t2_bool_id = word_.BoolId(t2)
|
| 224 | t2_bool_kind = consts.GetKind(t2_bool_id)
|
| 225 |
|
| 226 | #log('t2 %s / t2_bool_id %s / t2_bool_kind %s', t2, t2_bool_id, t2_bool_kind)
|
| 227 | # Op for < and >, -a and -o pun
|
| 228 | if t2_bool_kind == Kind.BoolBinary or t2_bool_id in (Id.Op_Less,
|
| 229 | Id.Op_Great):
|
| 230 | left = self.cur_word
|
| 231 |
|
| 232 | self._Next()
|
| 233 | op = self.bool_id
|
| 234 |
|
| 235 | if t2_bool_id == Id.BoolBinary_EqualTilde:
|
| 236 | self._Next(lex_mode=lex_mode_e.BashRegex)
|
| 237 | else:
|
| 238 | self._Next()
|
| 239 |
|
| 240 | right = self.cur_word
|
| 241 | self._Next()
|
| 242 |
|
| 243 | tilde = word_.TildeDetect(left)
|
| 244 | if tilde:
|
| 245 | left = tilde
|
| 246 | tilde = word_.TildeDetect(right)
|
| 247 | if tilde:
|
| 248 | right = tilde
|
| 249 |
|
| 250 | return bool_expr.Binary(op, left, right)
|
| 251 |
|
| 252 | else: # [[ foo ]]
|
| 253 | w = self.cur_word
|
| 254 | tilde = word_.TildeDetect(w)
|
| 255 | if tilde:
|
| 256 | w = tilde
|
| 257 | self._Next()
|
| 258 | return bool_expr.WordTest(w)
|
| 259 |
|
| 260 | if self.bool_id == Id.Op_LParen:
|
| 261 | self._Next()
|
| 262 | node = self.ParseExpr()
|
| 263 | if self.bool_id != Id.Op_RParen:
|
| 264 | p_die('Expected ), got %s' % word_.Pretty(self.cur_word),
|
| 265 | loc.Word(self.cur_word))
|
| 266 | self._Next()
|
| 267 | return node
|
| 268 |
|
| 269 | # It's not WORD, UNARY_OP, or '('
|
| 270 | p_die(
|
| 271 | 'Unexpected token in boolean expression (%s)' %
|
| 272 | ui.PrettyId(self.bool_id), loc.Word(self.cur_word))
|