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 17import ( 18 "bytes" 19 "fmt" 20 "os" 21 "path/filepath" 22 "regexp" 23 "runtime" 24 "sort" 25 "strings" 26 "time" 27 28 "github.com/golang/glog" 29) 30 31type nodeState int 32 33const ( 34 nodeInit nodeState = iota // not visited 35 nodeVisit // visited 36 nodeFile // visited & file exists 37 nodeAlias // visited & alias for other target 38 nodeMissing // visited & no target for this output 39 nodeBuild // visited & build emitted 40) 41 42func (s nodeState) String() string { 43 switch s { 44 case nodeInit: 45 return "node-init" 46 case nodeVisit: 47 return "node-visit" 48 case nodeFile: 49 return "node-file" 50 case nodeAlias: 51 return "node-alias" 52 case nodeMissing: 53 return "node-missing" 54 case nodeBuild: 55 return "node-build" 56 default: 57 return fmt.Sprintf("node-unknown[%d]", int(s)) 58 } 59} 60 61// NinjaGenerator generates ninja build files from DepGraph. 62type NinjaGenerator struct { 63 // Args is original arguments to generate the ninja file. 64 Args []string 65 // Suffix is suffix for generated files. 66 Suffix string 67 // GomaDir is goma directory. If empty, goma will not be used. 68 GomaDir string 69 // DetectAndroidEcho detects echo as description. 70 DetectAndroidEcho bool 71 72 f *os.File 73 nodes []*DepNode 74 exports map[string]bool 75 76 ctx *execContext 77 78 ruleID int 79 done map[string]nodeState 80} 81 82func (n *NinjaGenerator) init(g *DepGraph) { 83 g.resolveVPATH() 84 n.nodes = g.nodes 85 n.exports = g.exports 86 n.ctx = newExecContext(g.vars, g.vpaths, true) 87 n.done = make(map[string]nodeState) 88} 89 90func getDepfileImpl(ss string) (string, error) { 91 tss := ss + " " 92 if (!strings.Contains(tss, " -MD ") && !strings.Contains(tss, " -MMD ")) || !strings.Contains(tss, " -c ") { 93 return "", nil 94 } 95 96 mfIndex := strings.Index(ss, " -MF ") 97 if mfIndex >= 0 { 98 mf := trimLeftSpace(ss[mfIndex+4:]) 99 if strings.Index(mf, " -MF ") >= 0 { 100 return "", fmt.Errorf("Multiple output file candidates in %s", ss) 101 } 102 mfEndIndex := strings.IndexAny(mf, " \t\n") 103 if mfEndIndex >= 0 { 104 mf = mf[:mfEndIndex] 105 } 106 107 return mf, nil 108 } 109 110 outIndex := strings.Index(ss, " -o ") 111 if outIndex < 0 { 112 return "", fmt.Errorf("Cannot find the depfile in %s", ss) 113 } 114 out := trimLeftSpace(ss[outIndex+4:]) 115 if strings.Index(out, " -o ") >= 0 { 116 return "", fmt.Errorf("Multiple output file candidates in %s", ss) 117 } 118 outEndIndex := strings.IndexAny(out, " \t\n") 119 if outEndIndex >= 0 { 120 out = out[:outEndIndex] 121 } 122 return stripExt(out) + ".d", nil 123} 124 125// getDepfile gets depfile from cmdline, and returns cmdline and depfile. 126func getDepfile(cmdline string) (string, string, error) { 127 // A hack for Android - llvm-rs-cc seems not to emit a dep file. 128 if strings.Contains(cmdline, "bin/llvm-rs-cc ") { 129 return cmdline, "", nil 130 } 131 132 depfile, err := getDepfileImpl(cmdline) 133 if depfile == "" || err != nil { 134 return cmdline, depfile, err 135 } 136 137 // A hack for Makefiles generated by automake. 138 mvCmd := "(mv -f " + depfile + " " 139 if i := strings.LastIndex(cmdline, mvCmd); i >= 0 { 140 rest := cmdline[i+len(mvCmd):] 141 ei := strings.IndexByte(rest, ')') 142 if ei < 0 { 143 return cmdline, "", fmt.Errorf("unbalanced parenthes? %s", cmdline) 144 } 145 cmdline = cmdline[:i] + "(cp -f " + depfile + " " + rest 146 return cmdline, depfile, nil 147 } 148 149 // A hack for Android to get .P files instead of .d. 150 p := stripExt(depfile) + ".P" 151 if strings.Contains(cmdline, p) { 152 rmfCmd := "; rm -f " + depfile 153 ncmdline := strings.Replace(cmdline, rmfCmd, "", 1) 154 if ncmdline == cmdline { 155 return cmdline, "", fmt.Errorf("cannot find removal of .d file: %s", cmdline) 156 } 157 return ncmdline, p, nil 158 } 159 160 // A hack for Android. For .s files, GCC does not use 161 // C preprocessor, so it ignores -MF flag. 162 as := "/" + stripExt(filepath.Base(depfile)) + ".s" 163 if strings.Contains(cmdline, as) { 164 return cmdline, "", nil 165 } 166 167 cmdline += fmt.Sprintf(" && cp %s %s.tmp", depfile, depfile) 168 depfile += ".tmp" 169 return cmdline, depfile, nil 170} 171 172func trimTailingSlash(s string) string { 173 if s == "" { 174 return s 175 } 176 if s[len(s)-1] != '\\' { 177 return s 178 } 179 // drop single trailing slash - multiline_arg.mk 180 if len(s) > 2 && s[len(s)-2] != '\\' { 181 return s[:len(s)-1] 182 } 183 // preserve two trailing slash - escaped_backslash.mk 184 return s 185} 186 187func stripShellComment(s string) string { 188 if strings.IndexByte(s, '#') < 0 { 189 // Fast path. 190 return s 191 } 192 // set space as an initial value so the leading comment will be 193 // stripped out. 194 lastch := rune(' ') 195 var escape bool 196 var quote rune 197 var skip rune 198 var cmdsubst []rune 199 var buf bytes.Buffer 200Loop: 201 for _, c := range s { 202 if skip != 0 { 203 if skip != c { 204 continue Loop 205 } 206 if len(cmdsubst) > 0 && cmdsubst[len(cmdsubst)-1] == skip { 207 cmdsubst = cmdsubst[:len(cmdsubst)-1] 208 } 209 skip = 0 210 } 211 if quote != 0 { 212 if quote == c && (quote == '\'' || !escape) { 213 quote = 0 214 } 215 } else if !escape { 216 if c == '#' && isWhitespace(lastch) { 217 if len(cmdsubst) == 0 { 218 // strip comment until the end of line. 219 skip = '\n' 220 continue Loop 221 } 222 // strip comment until the end of command subst. 223 skip = cmdsubst[len(cmdsubst)-1] 224 continue Loop 225 } else if c == '\'' || c == '"' { 226 quote = c 227 } else if lastch == '$' && c == '(' { 228 cmdsubst = append(cmdsubst, ')') 229 } else if c == '`' { 230 cmdsubst = append(cmdsubst, '`') 231 } 232 } 233 if escape { 234 escape = false 235 } else if c == '\\' { 236 escape = true 237 } else { 238 escape = false 239 } 240 lastch = c 241 buf.WriteRune(c) 242 } 243 return buf.String() 244} 245 246var ccRE = regexp.MustCompile(`^prebuilts/(gcc|clang)/.*(gcc|g\+\+|clang|clang\+\+) .* ?-c `) 247 248func gomaCmdForAndroidCompileCmd(cmd string) (string, bool) { 249 i := strings.Index(cmd, " ") 250 if i < 0 { 251 return cmd, false 252 } 253 driver := cmd[:i] 254 if strings.HasSuffix(driver, "ccache") { 255 return gomaCmdForAndroidCompileCmd(cmd[i+1:]) 256 } 257 return cmd, ccRE.MatchString(cmd) 258} 259 260func descriptionFromCmd(cmd string) (string, bool) { 261 if !strings.HasPrefix(cmd, "echo") || !isWhitespace(rune(cmd[4])) { 262 return "", false 263 } 264 echoarg := cmd[5:] 265 266 // strip outer quotes, and fail if it is not a single echo command. 267 var buf bytes.Buffer 268 var escape bool 269 var quote rune 270 for _, c := range echoarg { 271 if escape { 272 escape = false 273 buf.WriteRune(c) 274 continue 275 } 276 if c == '\\' { 277 escape = true 278 buf.WriteRune(c) 279 continue 280 } 281 if quote != 0 { 282 if c == quote { 283 quote = 0 284 continue 285 } 286 buf.WriteRune(c) 287 continue 288 } 289 switch c { 290 case '\'', '"', '`': 291 quote = c 292 case '<', '>', '&', '|', ';': 293 return "", false 294 default: 295 buf.WriteRune(c) 296 } 297 } 298 return buf.String(), true 299} 300 301func (n *NinjaGenerator) genShellScript(runners []runner) (cmd string, desc string, useLocalPool bool) { 302 const defaultDesc = "build $out" 303 var useGomacc bool 304 var buf bytes.Buffer 305 for i, r := range runners { 306 if i > 0 { 307 if runners[i-1].ignoreError { 308 buf.WriteString(" ; ") 309 } else { 310 buf.WriteString(" && ") 311 } 312 } 313 cmd := trimTailingSlash(r.cmd) 314 cmd = stripShellComment(cmd) 315 cmd = trimLeftSpace(cmd) 316 cmd = strings.Replace(cmd, "\\\n\t", "", -1) 317 cmd = strings.Replace(cmd, "\\\n", "", -1) 318 cmd = strings.TrimRight(cmd, " \t\n;") 319 cmd = escapeNinja(cmd) 320 if cmd == "" { 321 cmd = "true" 322 } 323 glog.V(2).Infof("cmd %q=>%q", r.cmd, cmd) 324 if n.GomaDir != "" { 325 rcmd, ok := gomaCmdForAndroidCompileCmd(cmd) 326 if ok { 327 cmd = fmt.Sprintf("%s/gomacc %s", n.GomaDir, rcmd) 328 useGomacc = true 329 } 330 } 331 if n.DetectAndroidEcho && desc == "" { 332 d, ok := descriptionFromCmd(cmd) 333 if ok { 334 desc = d 335 cmd = "true" 336 } 337 } 338 needsSubShell := i > 0 || len(runners) > 1 339 if cmd[0] == '(' { 340 needsSubShell = false 341 } 342 343 if needsSubShell { 344 buf.WriteByte('(') 345 } 346 buf.WriteString(cmd) 347 if i == len(runners)-1 && r.ignoreError { 348 buf.WriteString(" ; true") 349 } 350 if needsSubShell { 351 buf.WriteByte(')') 352 } 353 } 354 if desc == "" { 355 desc = defaultDesc 356 } 357 return buf.String(), desc, n.GomaDir != "" && !useGomacc 358} 359 360func (n *NinjaGenerator) genRuleName() string { 361 ruleName := fmt.Sprintf("rule%d", n.ruleID) 362 n.ruleID++ 363 return ruleName 364} 365 366func (n *NinjaGenerator) emitBuild(output, rule, inputs, orderOnlys string) { 367 fmt.Fprintf(n.f, "build %s: %s", escapeBuildTarget(output), rule) 368 if inputs != "" { 369 fmt.Fprintf(n.f, " %s", inputs) 370 } 371 if orderOnlys != "" { 372 fmt.Fprintf(n.f, " || %s", orderOnlys) 373 } 374} 375 376func escapeBuildTarget(s string) string { 377 i := strings.IndexAny(s, "$: \\") 378 if i < 0 { 379 return s 380 } 381 // unescapeInput only "\ ", "\=" unescape as " ", "=". 382 // TODO(ukai): which char should unescape, which should not here? 383 var esc rune 384 var buf bytes.Buffer 385 for _, c := range s { 386 switch c { 387 case '\\': 388 esc = c 389 continue 390 case '$', ':', ' ': 391 esc = 0 392 buf.WriteByte('$') 393 } 394 if esc != 0 { 395 buf.WriteRune(esc) 396 esc = 0 397 } 398 buf.WriteRune(c) 399 } 400 if esc != 0 { 401 buf.WriteRune(esc) 402 } 403 return buf.String() 404} 405 406func (n *NinjaGenerator) dependency(node *DepNode) (string, string) { 407 var deps []string 408 seen := make(map[string]bool) 409 for _, d := range node.Deps { 410 t := escapeBuildTarget(d.Output) 411 if seen[t] { 412 continue 413 } 414 deps = append(deps, t) 415 seen[t] = true 416 } 417 var orderOnlys []string 418 for _, d := range node.OrderOnlys { 419 t := escapeBuildTarget(d.Output) 420 if seen[t] { 421 continue 422 } 423 orderOnlys = append(orderOnlys, t) 424 seen[t] = true 425 } 426 return strings.Join(deps, " "), strings.Join(orderOnlys, " ") 427} 428 429func escapeNinja(s string) string { 430 return strings.Replace(s, "$", "$$", -1) 431} 432 433func escapeShell(s string) string { 434 i := strings.IndexAny(s, "$`!\\\"") 435 if i < 0 { 436 return s 437 } 438 var buf bytes.Buffer 439 var lastDollar bool 440 for _, c := range s { 441 switch c { 442 case '$': 443 if lastDollar { 444 buf.WriteRune(c) 445 lastDollar = false 446 continue 447 } 448 buf.WriteString(`\$`) 449 lastDollar = true 450 continue 451 case '`', '"', '!', '\\': 452 buf.WriteByte('\\') 453 } 454 buf.WriteRune(c) 455 lastDollar = false 456 } 457 return buf.String() 458} 459 460func (n *NinjaGenerator) ninjaVars(s string, nv [][]string, esc func(string) string) string { 461 for _, v := range nv { 462 k, v := v[0], v[1] 463 if v == "" { 464 continue 465 } 466 if strings.Contains(v, "/./") || strings.Contains(v, "/../") || strings.Contains(v, "$") { 467 // ninja will normalize paths (/./, /../), so keep it as is 468 // ninja will emit quoted string for $ 469 continue 470 } 471 if esc != nil { 472 v = esc(v) 473 } 474 s = strings.Replace(s, v, k, -1) 475 } 476 return s 477} 478 479func (n *NinjaGenerator) emitNode(node *DepNode) error { 480 output := node.Output 481 if _, found := n.done[output]; found { 482 return nil 483 } 484 n.done[output] = nodeVisit 485 486 if len(node.Cmds) == 0 && len(node.Deps) == 0 && len(node.OrderOnlys) == 0 && !node.IsPhony { 487 if _, ok := n.ctx.vpaths.exists(output); ok { 488 n.done[output] = nodeFile 489 return nil 490 } 491 o := filepath.Clean(output) 492 if o != output { 493 // if normalized target has been done, it marks as alias. 494 if s, found := n.done[o]; found { 495 glog.V(1).Infof("node %s=%s => %s=alias", o, s, node.Output) 496 n.done[output] = nodeAlias 497 return nil 498 } 499 } 500 if node.Filename == "" { 501 n.done[output] = nodeMissing 502 } 503 return nil 504 } 505 506 runners, _, err := createRunners(n.ctx, node) 507 if err != nil { 508 return err 509 } 510 ruleName := "phony" 511 useLocalPool := false 512 inputs, orderOnlys := n.dependency(node) 513 if len(runners) > 0 { 514 ruleName = n.genRuleName() 515 fmt.Fprintf(n.f, "\n# rule for %q\n", node.Output) 516 fmt.Fprintf(n.f, "rule %s\n", ruleName) 517 518 ss, desc, ulp := n.genShellScript(runners) 519 if ulp { 520 useLocalPool = true 521 } 522 fmt.Fprintf(n.f, " description = %s\n", desc) 523 cmdline, depfile, err := getDepfile(ss) 524 if err != nil { 525 return err 526 } 527 if depfile != "" { 528 fmt.Fprintf(n.f, " depfile = %s\n", depfile) 529 fmt.Fprintf(n.f, " deps = gcc\n") 530 } 531 nv := [][]string{ 532 []string{"${in}", inputs}, 533 []string{"${out}", escapeNinja(output)}, 534 } 535 // It seems Linux is OK with ~130kB. 536 // TODO: Find this number automatically. 537 ArgLenLimit := 100 * 1000 538 if len(cmdline) > ArgLenLimit { 539 fmt.Fprintf(n.f, " rspfile = $out.rsp\n") 540 cmdline = n.ninjaVars(cmdline, nv, nil) 541 fmt.Fprintf(n.f, " rspfile_content = %s\n", cmdline) 542 fmt.Fprintf(n.f, " command = %s $out.rsp\n", n.ctx.shell) 543 } else { 544 cmdline = escapeShell(cmdline) 545 cmdline = n.ninjaVars(cmdline, nv, escapeShell) 546 fmt.Fprintf(n.f, " command = %s -c \"%s\"\n", n.ctx.shell, cmdline) 547 } 548 } 549 n.emitBuild(output, ruleName, inputs, orderOnlys) 550 if useLocalPool { 551 fmt.Fprintf(n.f, " pool = local_pool\n") 552 } 553 fmt.Fprintf(n.f, "\n") 554 n.done[output] = nodeBuild 555 556 for _, d := range node.Deps { 557 err := n.emitNode(d) 558 if err != nil { 559 return err 560 } 561 glog.V(1).Infof("node %s dep node %q %s", node.Output, d.Output, n.done[d.Output]) 562 } 563 for _, d := range node.OrderOnlys { 564 err := n.emitNode(d) 565 if err != nil { 566 return err 567 } 568 glog.V(1).Infof("node %s order node %q %s", node.Output, d.Output, n.done[d.Output]) 569 } 570 return nil 571} 572 573func (n *NinjaGenerator) emitRegenRules() error { 574 if len(n.Args) == 0 { 575 return nil 576 } 577 mkfiles, err := n.ctx.ev.EvaluateVar("MAKEFILE_LIST") 578 if err != nil { 579 return err 580 } 581 fmt.Fprintf(n.f, ` 582rule regen_ninja 583 description = Regenerate ninja files due to dependency 584 generator=1 585 command=%s 586`, strings.Join(n.Args, " ")) 587 fmt.Fprintf(n.f, "build %s: regen_ninja %s", n.ninjaName(), mkfiles) 588 // TODO: Add dependencies to directories read by $(wildcard) or 589 // $(shell find). 590 if len(usedEnvs) > 0 { 591 fmt.Fprintf(n.f, " %s", n.envlistName()) 592 } 593 fmt.Fprintf(n.f, "\n\n") 594 return nil 595} 596 597func (n *NinjaGenerator) shName() string { 598 return fmt.Sprintf("ninja%s.sh", n.Suffix) 599} 600 601func (n *NinjaGenerator) ninjaName() string { 602 return fmt.Sprintf("build%s.ninja", n.Suffix) 603} 604 605func (n *NinjaGenerator) envlistName() string { 606 return fmt.Sprintf(".kati_env%s", n.Suffix) 607} 608 609func (n *NinjaGenerator) generateEnvlist() (err error) { 610 f, err := os.Create(n.envlistName()) 611 if err != nil { 612 return err 613 } 614 defer func() { 615 cerr := f.Close() 616 if err == nil { 617 err = cerr 618 } 619 }() 620 for k := range usedEnvs { 621 v, err := n.ctx.ev.EvaluateVar(k) 622 if err != nil { 623 return err 624 } 625 fmt.Fprintf(f, "%q=%q\n", k, v) 626 } 627 return nil 628} 629 630func (n *NinjaGenerator) generateShell() (err error) { 631 f, err := os.Create(n.shName()) 632 if err != nil { 633 return err 634 } 635 defer func() { 636 cerr := f.Close() 637 if err == nil { 638 err = cerr 639 } 640 }() 641 642 fmt.Fprintf(f, "#!/bin/bash\n") 643 fmt.Fprintf(f, "# Generated by kati %s\n", gitVersion) 644 fmt.Fprintln(f) 645 fmt.Fprintln(f, `cd $(dirname "$0")`) 646 if n.Suffix != "" { 647 fmt.Fprintf(f, "if [ -f %s ]; then\n export $(cat %s)\nfi\n", n.envlistName(), n.envlistName()) 648 } 649 for name, export := range n.exports { 650 // export "a b"=c will error on bash 651 // bash: export `a b=c': not a valid identifier 652 if strings.ContainsAny(name, " \t\n\r") { 653 glog.V(1).Infof("ignore export %q (export:%t)", name, export) 654 continue 655 } 656 if export { 657 v, err := n.ctx.ev.EvaluateVar(name) 658 if err != nil { 659 return err 660 } 661 fmt.Fprintf(f, "export %q=%q\n", name, v) 662 } else { 663 fmt.Fprintf(f, "unset %q\n", name) 664 } 665 } 666 if n.GomaDir == "" { 667 fmt.Fprintf(f, `exec ninja -f %s "$@"`+"\n", n.ninjaName()) 668 } else { 669 fmt.Fprintf(f, `exec ninja -f %s -j500 "$@"`+"\n", n.ninjaName()) 670 } 671 672 return f.Chmod(0755) 673} 674 675func (n *NinjaGenerator) generateNinja(defaultTarget string) (err error) { 676 f, err := os.Create(n.ninjaName()) 677 if err != nil { 678 return err 679 } 680 defer func() { 681 cerr := f.Close() 682 if err == nil { 683 err = cerr 684 } 685 }() 686 687 n.f = f 688 fmt.Fprintf(n.f, "# Generated by kati %s\n", gitVersion) 689 fmt.Fprintf(n.f, "\n") 690 691 if len(usedEnvs) > 0 { 692 fmt.Fprintln(n.f, "# Environment variables used:") 693 var names []string 694 for name := range usedEnvs { 695 names = append(names, name) 696 } 697 sort.Strings(names) 698 for _, name := range names { 699 v, err := n.ctx.ev.EvaluateVar(name) 700 if err != nil { 701 return err 702 } 703 fmt.Fprintf(n.f, "# %q=%q\n", name, v) 704 } 705 fmt.Fprintf(n.f, "\n") 706 } 707 708 if n.GomaDir != "" { 709 fmt.Fprintf(n.f, "pool local_pool\n") 710 fmt.Fprintf(n.f, " depth = %d\n\n", runtime.NumCPU()) 711 } 712 713 err = n.emitRegenRules() 714 if err != nil { 715 return err 716 } 717 718 // defining $out for $@ and $in for $^ here doesn't work well, 719 // because these texts will be processed in escapeShell... 720 for _, node := range n.nodes { 721 err := n.emitNode(node) 722 if err != nil { 723 return err 724 } 725 glog.V(1).Infof("node %q %s", node.Output, n.done[node.Output]) 726 } 727 728 // emit phony targets for visited nodes that are 729 // - not existing file 730 // - not alias for other targets. 731 var nodes []string 732 for node, state := range n.done { 733 if state != nodeVisit { 734 continue 735 } 736 nodes = append(nodes, node) 737 } 738 if len(nodes) > 0 { 739 fmt.Fprintln(n.f) 740 sort.Strings(nodes) 741 for _, node := range nodes { 742 n.emitBuild(node, "phony", "", "") 743 fmt.Fprintln(n.f) 744 n.done[node] = nodeBuild 745 } 746 } 747 748 // emit default if the target was emitted. 749 if defaultTarget != "" && n.done[defaultTarget] == nodeBuild { 750 fmt.Fprintf(n.f, "\ndefault %s\n", escapeNinja(defaultTarget)) 751 } 752 return nil 753} 754 755// Save generates build.ninja from DepGraph. 756func (n *NinjaGenerator) Save(g *DepGraph, name string, targets []string) error { 757 startTime := time.Now() 758 n.init(g) 759 err := n.generateEnvlist() 760 if err != nil { 761 return err 762 } 763 err = n.generateShell() 764 if err != nil { 765 return err 766 } 767 var defaultTarget string 768 if len(targets) == 0 && len(g.nodes) > 0 { 769 defaultTarget = g.nodes[0].Output 770 } 771 err = n.generateNinja(defaultTarget) 772 if err != nil { 773 return err 774 } 775 logStats("generate ninja time: %q", time.Since(startTime)) 776 return nil 777} 778