1// Copyright 2015 Google Inc. All rights reserved 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 15package kati 16 17//go:generate go run testcase/gen_testcase_parse_benchmark.go 18// 19// $ go generate 20// $ go test -bench . 21 22import ( 23 "bufio" 24 "bytes" 25 "crypto/sha1" 26 "errors" 27 "fmt" 28 "io" 29 "io/ioutil" 30 "strings" 31 "sync" 32 "time" 33 34 "github.com/golang/glog" 35) 36 37type makefile struct { 38 filename string 39 stmts []ast 40} 41 42type ifState struct { 43 ast *ifAST 44 inElse bool 45 numNest int 46} 47 48type parser struct { 49 rd *bufio.Reader 50 mk makefile 51 lineno int 52 elineno int // lineno == elineno unless there is trailing '\'. 53 linenoFixed bool 54 done bool 55 outStmts *[]ast 56 inRecipe bool 57 ifStack []ifState 58 59 defineVar []byte 60 inDef []byte 61 62 defOpt string 63 numIfNest int 64 err error 65} 66 67func newParser(rd io.Reader, filename string) *parser { 68 p := &parser{ 69 rd: bufio.NewReader(rd), 70 } 71 p.mk.filename = filename 72 p.outStmts = &p.mk.stmts 73 return p 74} 75 76func (p *parser) srcpos() srcpos { 77 return srcpos{ 78 filename: p.mk.filename, 79 lineno: p.lineno, 80 } 81} 82 83func (p *parser) addStatement(stmt ast) { 84 *p.outStmts = append(*p.outStmts, stmt) 85 switch stmt.(type) { 86 case *maybeRuleAST: 87 p.inRecipe = true 88 case *assignAST, *includeAST, *exportAST: 89 p.inRecipe = false 90 } 91} 92 93func (p *parser) readLine() []byte { 94 if !p.linenoFixed { 95 p.lineno = p.elineno + 1 96 } 97 var line []byte 98 for !p.done { 99 buf, err := p.rd.ReadBytes('\n') 100 if !p.linenoFixed { 101 p.elineno++ 102 } 103 if err == io.EOF { 104 p.done = true 105 } else if err != nil { 106 p.err = fmt.Errorf("readline %s: %v", p.srcpos(), err) 107 p.done = true 108 } 109 line = append(line, buf...) 110 buf = bytes.TrimRight(buf, "\r\n") 111 glog.V(4).Infof("buf:%q", buf) 112 backslash := false 113 for len(buf) > 0 && buf[len(buf)-1] == '\\' { 114 buf = buf[:len(buf)-1] 115 backslash = !backslash 116 } 117 if !backslash { 118 glog.V(4).Infof("no concat line:%q", buf) 119 break 120 } 121 } 122 line = bytes.TrimRight(line, "\r\n") 123 return line 124} 125 126func newAssignAST(p *parser, lhsBytes []byte, rhsBytes []byte, op string) (*assignAST, error) { 127 lhs, _, err := parseExpr(lhsBytes, nil, parseOp{alloc: true}) 128 if err != nil { 129 return nil, err 130 } 131 rhs, _, err := parseExpr(rhsBytes, nil, parseOp{alloc: true}) 132 if err != nil { 133 return nil, err 134 } 135 opt := "" 136 if p != nil { 137 opt = p.defOpt 138 } 139 return &assignAST{ 140 lhs: lhs, 141 rhs: rhs, 142 op: op, 143 opt: opt, 144 }, nil 145} 146 147func (p *parser) handleDirective(line []byte, directives map[string]directiveFunc) bool { 148 w, data := firstWord(line) 149 if d, ok := directives[string(w)]; ok { 150 d(p, data) 151 return true 152 } 153 return false 154} 155 156func (p *parser) handleRuleOrAssign(line []byte) { 157 rline := line 158 var semi []byte 159 if i := findLiteralChar(line, ';', 0, skipVar); i >= 0 { 160 // preserve after semicolon 161 semi = append(semi, line[i+1:]...) 162 rline = concatline(line[:i]) 163 } else { 164 rline = concatline(line) 165 } 166 if p.handleAssign(line) { 167 return 168 } 169 // not assignment. 170 // ie. no '=' found or ':' found before '=' (except ':=') 171 p.parseMaybeRule(rline, semi) 172 return 173} 174 175func (p *parser) handleAssign(line []byte) bool { 176 aline, _ := removeComment(concatline(line)) 177 aline = trimLeftSpaceBytes(aline) 178 if len(aline) == 0 { 179 return false 180 } 181 // fmt.Printf("assign: %q=>%q\n", line, aline) 182 i := findLiteralChar(aline, ':', '=', skipVar) 183 if i >= 0 { 184 if aline[i] == '=' { 185 p.parseAssign(aline, i) 186 return true 187 } 188 if aline[i] == ':' && i+1 < len(aline) && aline[i+1] == '=' { 189 p.parseAssign(aline, i+1) 190 return true 191 } 192 } 193 return false 194} 195 196func (p *parser) parseAssign(line []byte, sep int) { 197 lhs, op, rhs := line[:sep], line[sep:sep+1], line[sep+1:] 198 if sep > 0 { 199 switch line[sep-1] { 200 case ':', '+', '?': 201 lhs, op = line[:sep-1], line[sep-1:sep+1] 202 } 203 } 204 glog.V(1).Infof("parseAssign %s op:%q opt:%s", line, op, p.defOpt) 205 lhs = trimSpaceBytes(lhs) 206 rhs = trimLeftSpaceBytes(rhs) 207 aast, err := newAssignAST(p, lhs, rhs, string(op)) 208 if err != nil { 209 p.err = err 210 return 211 } 212 aast.srcpos = p.srcpos() 213 p.addStatement(aast) 214} 215 216func (p *parser) parseMaybeRule(line, semi []byte) { 217 if len(line) == 0 { 218 p.err = p.srcpos().errorf("*** missing rule before commands.") 219 return 220 } 221 if line[0] == '\t' { 222 p.err = p.srcpos().errorf("*** commands commence before first target.") 223 return 224 } 225 var assign *assignAST 226 ci := findLiteralChar(line, ':', 0, skipVar) 227 if ci >= 0 { 228 eqi := findLiteralChar(line[ci+1:], '=', 0, skipVar) 229 if eqi == 0 { 230 panic(fmt.Sprintf("unexpected eq after colon: %q", line)) 231 } 232 if eqi > 0 { 233 var lhsbytes []byte 234 op := "=" 235 switch line[ci+1+eqi-1] { 236 case ':', '+', '?': 237 lhsbytes = append(lhsbytes, line[ci+1:ci+1+eqi-1]...) 238 op = string(line[ci+1+eqi-1 : ci+1+eqi+1]) 239 default: 240 lhsbytes = append(lhsbytes, line[ci+1:ci+1+eqi]...) 241 } 242 243 lhsbytes = trimSpaceBytes(lhsbytes) 244 lhs, _, err := parseExpr(lhsbytes, nil, parseOp{}) 245 if err != nil { 246 p.err = p.srcpos().error(err) 247 return 248 } 249 var rhsbytes []byte 250 rhsbytes = append(rhsbytes, line[ci+1+eqi+1:]...) 251 if semi != nil { 252 rhsbytes = append(rhsbytes, ';') 253 rhsbytes = append(rhsbytes, concatline(semi)...) 254 } 255 rhsbytes = trimLeftSpaceBytes(rhsbytes) 256 semi = nil 257 rhs, _, err := parseExpr(rhsbytes, nil, parseOp{}) 258 if err != nil { 259 p.err = p.srcpos().error(err) 260 return 261 } 262 263 // TODO(ukai): support override, export in target specific var. 264 assign = &assignAST{ 265 lhs: lhs, 266 rhs: rhs, 267 op: op, 268 } 269 assign.srcpos = p.srcpos() 270 line = line[:ci+1] 271 } 272 } 273 expr, _, err := parseExpr(line, nil, parseOp{}) 274 if err != nil { 275 p.err = p.srcpos().error(err) 276 return 277 } 278 // TODO(ukai): remove ast, and eval here. 279 rast := &maybeRuleAST{ 280 isRule: ci >= 0, 281 expr: expr, 282 assign: assign, 283 semi: semi, 284 } 285 rast.srcpos = p.srcpos() 286 glog.V(1).Infof("stmt: %#v", rast) 287 p.addStatement(rast) 288} 289 290func (p *parser) parseInclude(op string, line []byte) { 291 // TODO(ukai): parse expr here 292 iast := &includeAST{ 293 expr: string(line), 294 op: op, 295 } 296 iast.srcpos = p.srcpos() 297 p.addStatement(iast) 298} 299 300func (p *parser) parseIfdef(op string, data []byte) { 301 lhs, _, err := parseExpr(data, nil, parseOp{alloc: true}) 302 if err != nil { 303 p.err = p.srcpos().error(err) 304 return 305 } 306 iast := &ifAST{ 307 op: op, 308 lhs: lhs, 309 } 310 iast.srcpos = p.srcpos() 311 p.addStatement(iast) 312 p.ifStack = append(p.ifStack, ifState{ast: iast, numNest: p.numIfNest}) 313 p.outStmts = &iast.trueStmts 314} 315 316func (p *parser) parseTwoQuotes(s []byte) (string, string, []byte, bool) { 317 var args []string 318 for i := 0; i < 2; i++ { 319 s = trimSpaceBytes(s) 320 if len(s) == 0 { 321 return "", "", nil, false 322 } 323 quote := s[0] 324 if quote != '\'' && quote != '"' { 325 return "", "", nil, false 326 } 327 end := bytes.IndexByte(s[1:], quote) + 1 328 if end < 0 { 329 return "", "", nil, false 330 } 331 args = append(args, string(s[1:end])) 332 s = s[end+1:] 333 } 334 return args[0], args[1], s, true 335} 336 337// parse 338// "(lhs, rhs)" 339// "lhs, rhs" 340func (p *parser) parseEq(s []byte) (string, string, []byte, bool) { 341 if len(s) == 0 { 342 return "", "", nil, false 343 } 344 if s[0] == '(' { 345 in := s[1:] 346 glog.V(1).Infof("parseEq ( %q )", in) 347 term := []byte{','} 348 v, n, err := parseExpr(in, term, parseOp{matchParen: true}) 349 if err != nil { 350 glog.V(1).Infof("parse eq: %q: %v", in, err) 351 return "", "", nil, false 352 } 353 lhs := v.String() 354 n++ 355 n += skipSpaces(in[n:], nil) 356 term = []byte{')'} 357 in = in[n:] 358 v, n, err = parseExpr(in, term, parseOp{matchParen: true}) 359 if err != nil { 360 glog.V(1).Infof("parse eq 2nd: %q: %v", in, err) 361 return "", "", nil, false 362 } 363 rhs := v.String() 364 in = in[n+1:] 365 in = trimSpaceBytes(in) 366 return lhs, rhs, in, true 367 } 368 return p.parseTwoQuotes(s) 369} 370 371func (p *parser) parseIfeq(op string, data []byte) { 372 lhsBytes, rhsBytes, extra, ok := p.parseEq(data) 373 if !ok { 374 p.err = p.srcpos().errorf(`*** invalid syntax in conditional.`) 375 return 376 } 377 if len(extra) > 0 { 378 glog.V(1).Infof("extra %q", extra) 379 warnNoPrefix(p.srcpos(), `extraneous text after %q directive`, op) 380 } 381 382 lhs, _, err := parseExpr([]byte(lhsBytes), nil, parseOp{matchParen: true}) 383 if err != nil { 384 p.err = p.srcpos().error(err) 385 return 386 } 387 rhs, _, err := parseExpr([]byte(rhsBytes), nil, parseOp{matchParen: true}) 388 if err != nil { 389 p.err = p.srcpos().error(err) 390 return 391 } 392 393 iast := &ifAST{ 394 op: op, 395 lhs: lhs, 396 rhs: rhs, 397 } 398 iast.srcpos = p.srcpos() 399 p.addStatement(iast) 400 p.ifStack = append(p.ifStack, ifState{ast: iast, numNest: p.numIfNest}) 401 p.outStmts = &iast.trueStmts 402} 403 404func (p *parser) checkIfStack(curKeyword string) error { 405 if len(p.ifStack) == 0 { 406 return p.srcpos().errorf(`*** extraneous %q.`, curKeyword) 407 } 408 return nil 409} 410 411func (p *parser) parseElse(data []byte) { 412 err := p.checkIfStack("else") 413 if err != nil { 414 p.err = err 415 return 416 } 417 state := &p.ifStack[len(p.ifStack)-1] 418 if state.inElse { 419 p.err = p.srcpos().errorf(`*** only one "else" per conditional.`) 420 return 421 } 422 state.inElse = true 423 p.outStmts = &state.ast.falseStmts 424 425 nextIf := data 426 if len(nextIf) == 0 { 427 return 428 } 429 var ifDirectives = map[string]directiveFunc{ 430 "ifdef": ifdefDirective, 431 "ifndef": ifndefDirective, 432 "ifeq": ifeqDirective, 433 "ifneq": ifneqDirective, 434 } 435 p.numIfNest = state.numNest + 1 436 if p.handleDirective(nextIf, ifDirectives) { 437 p.numIfNest = 0 438 return 439 } 440 p.numIfNest = 0 441 warnNoPrefix(p.srcpos(), "extraneous text after `else' directive") 442 return 443} 444 445func (p *parser) parseEndif(data []byte) { 446 err := p.checkIfStack("endif") 447 if err != nil { 448 p.err = err 449 return 450 } 451 state := p.ifStack[len(p.ifStack)-1] 452 for t := 0; t <= state.numNest; t++ { 453 p.ifStack = p.ifStack[0 : len(p.ifStack)-1] 454 if len(p.ifStack) == 0 { 455 p.outStmts = &p.mk.stmts 456 } else { 457 state := p.ifStack[len(p.ifStack)-1] 458 if state.inElse { 459 p.outStmts = &state.ast.falseStmts 460 } else { 461 p.outStmts = &state.ast.trueStmts 462 } 463 } 464 } 465 if len(trimSpaceBytes(data)) > 0 { 466 warnNoPrefix(p.srcpos(), "extraneous text after `endif' directive") 467 } 468 return 469} 470 471func (p *parser) parseDefine(data []byte) { 472 p.defineVar = nil 473 p.inDef = nil 474 p.defineVar = append(p.defineVar, trimSpaceBytes(data)...) 475 return 476} 477 478func (p *parser) parseVpath(data []byte) { 479 vline, _ := removeComment(concatline(data)) 480 vline = trimLeftSpaceBytes(vline) 481 v, _, err := parseExpr(vline, nil, parseOp{}) 482 if err != nil { 483 p.err = p.srcpos().errorf("parse error %q: %v", string(vline), err) 484 return 485 } 486 vast := &vpathAST{ 487 expr: v, 488 } 489 vast.srcpos = p.srcpos() 490 p.addStatement(vast) 491} 492 493type directiveFunc func(*parser, []byte) 494 495var makeDirectives map[string]directiveFunc 496 497func init() { 498 makeDirectives = map[string]directiveFunc{ 499 "include": includeDirective, 500 "-include": sincludeDirective, 501 "sinclude": sincludeDirective, 502 "ifdef": ifdefDirective, 503 "ifndef": ifndefDirective, 504 "ifeq": ifeqDirective, 505 "ifneq": ifneqDirective, 506 "else": elseDirective, 507 "endif": endifDirective, 508 "define": defineDirective, 509 "override": overrideDirective, 510 "export": exportDirective, 511 "unexport": unexportDirective, 512 "vpath": vpathDirective, 513 } 514} 515 516func includeDirective(p *parser, data []byte) { 517 p.parseInclude("include", data) 518} 519 520func sincludeDirective(p *parser, data []byte) { 521 p.parseInclude("-include", data) 522} 523 524func ifdefDirective(p *parser, data []byte) { 525 p.parseIfdef("ifdef", data) 526} 527 528func ifndefDirective(p *parser, data []byte) { 529 p.parseIfdef("ifndef", data) 530} 531 532func ifeqDirective(p *parser, data []byte) { 533 p.parseIfeq("ifeq", data) 534} 535 536func ifneqDirective(p *parser, data []byte) { 537 p.parseIfeq("ifneq", data) 538} 539 540func elseDirective(p *parser, data []byte) { 541 p.parseElse(data) 542} 543 544func endifDirective(p *parser, data []byte) { 545 p.parseEndif(data) 546} 547 548func defineDirective(p *parser, data []byte) { 549 p.parseDefine(data) 550} 551 552func overrideDirective(p *parser, data []byte) { 553 p.defOpt = "override" 554 defineDirective := map[string]directiveFunc{ 555 "define": defineDirective, 556 } 557 glog.V(1).Infof("override define? %q", data) 558 if p.handleDirective(data, defineDirective) { 559 return 560 } 561 // e.g. overrider foo := bar 562 // line will be "foo := bar". 563 if p.handleAssign(data) { 564 return 565 } 566 p.defOpt = "" 567 var line []byte 568 line = append(line, []byte("override ")...) 569 line = append(line, data...) 570 p.handleRuleOrAssign(line) 571 // TODO(ukai): evaluate now to detect invalid "override" directive here? 572} 573 574func handleExport(p *parser, data []byte, export bool) (hasEqual bool) { 575 i := bytes.IndexByte(data, '=') 576 if i > 0 { 577 hasEqual = true 578 switch data[i-1] { 579 case ':', '+', '?': 580 i-- 581 } 582 data = data[:i] 583 } 584 east := &exportAST{ 585 expr: data, 586 hasEqual: hasEqual, 587 export: export, 588 } 589 east.srcpos = p.srcpos() 590 glog.V(1).Infof("export %v", east) 591 p.addStatement(east) 592 return hasEqual 593} 594 595func exportDirective(p *parser, data []byte) { 596 p.defOpt = "export" 597 defineDirective := map[string]directiveFunc{ 598 "define": defineDirective, 599 } 600 glog.V(1).Infof("export define? %q", data) 601 if p.handleDirective(data, defineDirective) { 602 return 603 } 604 605 if !handleExport(p, data, true) { 606 return 607 } 608 609 // e.g. export foo := bar 610 // line will be "foo := bar". 611 p.handleAssign(data) 612} 613 614func unexportDirective(p *parser, data []byte) { 615 handleExport(p, data, false) 616 return 617} 618 619func vpathDirective(p *parser, data []byte) { 620 p.parseVpath(data) 621} 622 623func (p *parser) parse() (mk makefile, err error) { 624 for !p.done { 625 line := p.readLine() 626 if glog.V(1) { 627 glog.Infof("%s: %q", p.srcpos(), line) 628 } 629 if p.defineVar != nil { 630 p.processDefine(line) 631 if p.err != nil { 632 return makefile{}, p.err 633 } 634 continue 635 } 636 p.defOpt = "" 637 if p.inRecipe { 638 if len(line) > 0 && line[0] == '\t' { 639 cast := &commandAST{cmd: string(line[1:])} 640 cast.srcpos = p.srcpos() 641 p.addStatement(cast) 642 continue 643 } 644 } 645 p.parseLine(line) 646 if p.err != nil { 647 return makefile{}, p.err 648 } 649 } 650 return p.mk, p.err 651} 652 653func (p *parser) parseLine(line []byte) { 654 cline := concatline(line) 655 if len(cline) == 0 { 656 return 657 } 658 if glog.V(1) { 659 glog.Infof("concatline:%q", cline) 660 } 661 var dline []byte 662 cline, _ = removeComment(cline) 663 dline = append(dline, cline...) 664 dline = trimSpaceBytes(dline) 665 if len(dline) == 0 { 666 return 667 } 668 if glog.V(1) { 669 glog.Infof("directive?: %q", dline) 670 } 671 if p.handleDirective(dline, makeDirectives) { 672 return 673 } 674 if glog.V(1) { 675 glog.Infof("rule or assign?: %q", line) 676 } 677 p.handleRuleOrAssign(line) 678} 679 680func (p *parser) processDefine(line []byte) { 681 line = append(line, '\n') 682 line = concatline(line) 683 if line[len(line)-1] != '\n' { 684 line = append(line, '\n') 685 } 686 if glog.V(1) { 687 glog.Infof("concatline:%q", line) 688 } 689 if !p.isEndef(line) { 690 p.inDef = append(p.inDef, line...) 691 if p.inDef == nil { 692 p.inDef = []byte{} 693 } 694 return 695 } 696 if p.inDef[len(p.inDef)-1] == '\n' { 697 p.inDef = p.inDef[:len(p.inDef)-1] 698 } 699 glog.V(1).Infof("multilineAssign %q %q", p.defineVar, p.inDef) 700 aast, err := newAssignAST(p, p.defineVar, p.inDef, "=") 701 if err != nil { 702 p.err = p.srcpos().errorf("assign error %q=%q: %v", p.defineVar, p.inDef, err) 703 return 704 } 705 aast.srcpos = p.srcpos() 706 aast.srcpos.lineno -= bytes.Count(p.inDef, []byte{'\n'}) 707 p.addStatement(aast) 708 p.defineVar = nil 709 p.inDef = nil 710 return 711} 712 713func (p *parser) isEndef(line []byte) bool { 714 if bytes.Equal(line, []byte("endef")) { 715 return true 716 } 717 w, data := firstWord(line) 718 if bytes.Equal(w, []byte("endef")) { 719 data, _ = removeComment(data) 720 data = trimLeftSpaceBytes(data) 721 if len(data) > 0 { 722 warnNoPrefix(p.srcpos(), `extraneous text after "endef" directive`) 723 } 724 return true 725 } 726 return false 727} 728 729func defaultMakefile() (string, error) { 730 candidates := []string{"GNUmakefile", "makefile", "Makefile"} 731 for _, filename := range candidates { 732 if exists(filename) { 733 return filename, nil 734 } 735 } 736 return "", errors.New("no targets specified and no makefile found") 737} 738 739func parseMakefileReader(rd io.Reader, loc srcpos) (makefile, error) { 740 parser := newParser(rd, loc.filename) 741 parser.lineno = loc.lineno 742 parser.elineno = loc.lineno 743 parser.linenoFixed = true 744 return parser.parse() 745} 746 747func parseMakefileString(s string, loc srcpos) (makefile, error) { 748 return parseMakefileReader(strings.NewReader(s), loc) 749} 750 751func parseMakefileBytes(s []byte, loc srcpos) (makefile, error) { 752 return parseMakefileReader(bytes.NewReader(s), loc) 753} 754 755type mkCacheEntry struct { 756 mk makefile 757 hash [sha1.Size]byte 758 err error 759 ts int64 760} 761 762type makefileCacheT struct { 763 mu sync.Mutex 764 mk map[string]mkCacheEntry 765} 766 767var makefileCache = &makefileCacheT{ 768 mk: make(map[string]mkCacheEntry), 769} 770 771func (mc *makefileCacheT) lookup(filename string) (makefile, [sha1.Size]byte, bool, error) { 772 var hash [sha1.Size]byte 773 mc.mu.Lock() 774 c, present := mc.mk[filename] 775 mc.mu.Unlock() 776 if !present { 777 return makefile{}, hash, false, nil 778 } 779 ts := getTimestamp(filename) 780 if ts < 0 || ts >= c.ts { 781 return makefile{}, hash, false, nil 782 } 783 return c.mk, c.hash, true, c.err 784} 785 786func (mc *makefileCacheT) parse(filename string) (makefile, [sha1.Size]byte, error) { 787 glog.Infof("parse Makefile %q", filename) 788 mk, hash, ok, err := makefileCache.lookup(filename) 789 if ok { 790 if glog.V(1) { 791 glog.Infof("makefile cache hit for %q", filename) 792 } 793 return mk, hash, err 794 } 795 if glog.V(1) { 796 glog.Infof("reading makefile %q", filename) 797 } 798 c, err := ioutil.ReadFile(filename) 799 if err != nil { 800 return makefile{}, hash, err 801 } 802 hash = sha1.Sum(c) 803 mk, err = parseMakefile(c, filename) 804 if err != nil { 805 return makefile{}, hash, err 806 } 807 makefileCache.mu.Lock() 808 makefileCache.mk[filename] = mkCacheEntry{ 809 mk: mk, 810 hash: hash, 811 err: err, 812 ts: time.Now().Unix(), 813 } 814 makefileCache.mu.Unlock() 815 return mk, hash, err 816} 817 818func parseMakefile(s []byte, filename string) (makefile, error) { 819 parser := newParser(bytes.NewReader(s), filename) 820 return parser.parse() 821} 822