aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
blob: 38cbb7c35f08a91a4ead62070d6030e2cac11562 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
// Copyright 2014 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package com.google.devtools.build.lib.syntax;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.events.EventHandler;
import com.google.devtools.build.lib.events.EventKind;
import com.google.devtools.build.lib.events.Location;
import com.google.devtools.build.lib.syntax.Mutability.Freezable;
import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
import com.google.devtools.build.lib.util.Fingerprint;
import com.google.devtools.build.lib.util.Pair;
import com.google.devtools.build.lib.util.Preconditions;
import com.google.devtools.build.lib.util.SpellChecker;
import com.google.devtools.common.options.Options;
import java.io.Serializable;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import javax.annotation.Nullable;

/**
 * An Environment is the main entry point to evaluating code in the BUILD language or Skylark. It
 * embodies all the state that is required to evaluate such code, except for the current instruction
 * pointer, which is an {@link ASTNode} whose {@link Statement#exec exec} or {@link Expression#eval
 * eval} method is invoked with this Environment, in a straightforward direct-style AST-walking
 * interpreter. {@link Continuation}-s are explicitly represented, but only partly, with another
 * part being implicit in a series of try-catch statements, to maintain the direct style. One
 * notable trick is how a {@link UserDefinedFunction} implements returning values as the function
 * catching a {@link ReturnStatement.ReturnException} thrown by a {@link ReturnStatement} in the
 * body.
 *
 * <p>Every Environment has a {@link Mutability} field, and must be used within a function that
 * creates and closes this {@link Mutability} with the try-with-resource pattern. This {@link
 * Mutability} is also used when initializing mutable objects within that Environment; when closed
 * at the end of the computation freezes the Environment and all those objects that then become
 * forever immutable. The pattern enforces the discipline that there should be no dangling mutable
 * Environment, or concurrency between interacting Environment-s. It is also an error to try to
 * mutate an Environment and its objects from another Environment, before the {@link Mutability} is
 * closed.
 *
 * <p>One creates an Environment using the {@link #builder} function, then populates it with {@link
 * #setup}, {@link #setupDynamic} and sometimes {@link #setupOverride}, before to evaluate code in
 * it with {@link BuildFileAST#eval}, or with {@link BuildFileAST#exec} (where the AST was obtained
 * by passing a {@link ValidationEnvironment} constructed from the Environment to {@link
 * BuildFileAST#parseBuildFile} or {@link BuildFileAST#parseSkylarkFile}). When the computation is
 * over, the frozen Environment can still be queried with {@link #lookup}.
 *
 * <p>Final fields of an Environment represent its dynamic state, i.e. state that remains the same
 * throughout a given evaluation context, and don't change with source code location, while mutable
 * fields embody its static state, that change with source code location. The seeming paradox is
 * that the words "dynamic" and "static" refer to the point of view of the source code, and here we
 * have a dual point of view.
 */
public final class Environment implements Freezable {

  /**
   * A phase for enabling or disabling certain builtin functions
   */
  public enum Phase { WORKSPACE, LOADING, ANALYSIS }

  /**
   * A mapping of bindings, along with a {@link Mutability} and a parent {@code Frame} from which to
   * inherit bindings. The order of the bindings within a single {@code Frame} is deterministic but
   * unspecified.
   *
   * <p>Each {@code Frame} can be thought of as either a lexical scope or a scope containing
   * predefined variables. Bindings in a {@code Frame} may shadow those inherited from its parents.
   * Thus, the chain of {@code Frame}s can represent a hierarchy of enclosing scopes, or a
   * collection of builtin modules with a linear precedence ordering.
   *
   * <p>Any non-frozen {@code Frame} must have the same {@code Mutability} as the current {@link
   * Environment}, to avoid interference from other evaluation contexts. For example, a {@link
   * UserDefinedFunction} will close over the global frame of the {@code Environment} in which it
   * was defined. When the function is called from other {@code Environment}s (possibly
   * simultaneously), that global frame must already be frozen; a new local {@code Frame} is created
   * to represent the lexical scope of the function.
   */
  public static final class Frame implements Freezable {

    private final Mutability mutability;

    @Nullable
    private final Frame parent;

    // If this frame is a global frame, the label for the corresponding target, e.g. //foo:bar.bzl.
    @Nullable
    private final Label label;

    private final Map<String, Object> bindings;

    public Frame(Mutability mutability) {
      this(mutability, null, null);
    }

    public Frame(Mutability mutability, Frame parent) {
      this(mutability, parent, null);
    }

    public Frame(Mutability mutability, Frame parent, Label label) {
      this.mutability = mutability;
      this.parent = parent;
      this.label = label;
      this.bindings = new LinkedHashMap<>();
    }

    public Frame(Mutability mutability, Frame parent, Label label, Map<String, Object> bindings) {
      this(mutability, parent, label);
      this.bindings.putAll(bindings);
    }

    /**
     * Returns a new {@code Frame} that is a copy of this one, but with {@code label} set to the
     * given value.
     */
    public Frame withLabel(Label label) {
      return new Frame(mutability, this, label);
    }

    /**
     * Returns the {@link Mutability} of this {@code Frame}, which may be different from its
     * parent's.
     */
    @Override
    public Mutability mutability() {
      return mutability;
    }

    /** Returns the parent {@code Frame}, if it exists. */
    @Nullable
    public Frame getParent() {
      return parent;
    }

    /**
     * Returns the label of this {@code Frame}, which may be null. Parent labels are not consulted.
     *
     * <p>Usually you want to use {@link #getTransitiveLabel}; this is just an accessor for
     * completeness.
     */
    @Nullable
    public Label getLabel() {
      return label;
    }

    /**
     * Walks from this {@code Frame} up through transitive parents, and returns the first non-null
     * label found, or null if all labels are null.
     */
    @Nullable
    public Label getTransitiveLabel() {
      if (label != null) {
        return label;
      } else if (parent != null) {
        return parent.getTransitiveLabel();
      } else {
        return null;
      }
    }

    /**
     * Returns a map of direct bindings of this {@code Frame}, ignoring parents.
     *
     * <p>For efficiency an unmodifiable view is returned. Callers should assume that the view is
     * invalidated by any subsequent modification to the {@code Frame}'s bindings.
     */
    public Map<String, Object> getBindings() {
      return Collections.unmodifiableMap(bindings);
    }

    /**
     * Returns a map containing all bindings of this {@code Frame} and of its transitive parents,
     * taking into account shadowing precedence.
     */
    public Map<String, Object> getTransitiveBindings() {
      // Can't use ImmutableMap.Builder because it doesn't allow duplicates.
      HashMap<String, Object> collectedBindings = new HashMap<>();
      accumulateTransitiveBindings(collectedBindings);
      return collectedBindings;
    }

    private void accumulateTransitiveBindings(Map<String, Object> accumulator) {
      // Put parents first, so child bindings take precedence.
      if (parent != null) {
        parent.accumulateTransitiveBindings(accumulator);
      }
      accumulator.putAll(bindings);
    }

    /**
     * Gets a binding from the current {@code Frame} or one of its transitive parents.
     *
     * <p>In case of conflicts, the binding found in the {@code Frame} closest to the current one is
     * used; the remaining bindings are shadowed.
     *
     * @param varname the name of the variable to be bound
     * @return the value bound to the variable, or null if no binding is found
     */
    public Object get(String varname) {
      if (bindings.containsKey(varname)) {
        return bindings.get(varname);
      }
      if (parent != null) {
        return parent.get(varname);
      }
      return null;
    }

    /**
     * Assigns or reassigns a binding in the current {@code Frame}.
     *
     * <p>If the binding has the same name as one in a transitive parent, the parent binding is
     * shadowed (i.e., the parent is unaffected).
     *
     * @param env the {@link Environment} attempting the mutation
     * @param varname the name of the variable to be bound
     * @param value the value to bind to the variable
     */
    public void put(Environment env, String varname, Object value)
        throws MutabilityException {
      Mutability.checkMutable(this, env);
      bindings.put(varname, value);
    }

    /**
     * TODO(laurentlb): Remove this method when possible. It should probably not
     * be part of the public interface.
     */
    void remove(Environment env, String varname) throws MutabilityException {
      Mutability.checkMutable(this, env);
      bindings.remove(varname);
    }

    @Override
    public String toString() {
      return String.format("<Frame%s>", mutability());
    }
  }

  /**
   * A Continuation contains data saved during a function call and restored when the function exits.
   */
  private static final class Continuation {
    /** The {@link BaseFunction} being evaluated that will return into this Continuation. */
    final BaseFunction function;

    /** The {@link FuncallExpression} to which this Continuation will return. */
    final FuncallExpression caller;

    /** The next Continuation after this Continuation. */
    @Nullable final Continuation continuation;

    /** The lexical Frame of the caller. */
    final Frame lexicalFrame;

    /** The global Frame of the caller. */
    final Frame globalFrame;

    /** The set of known global variables of the caller. */
    @Nullable final Set<String> knownGlobalVariables;

    Continuation(
        Continuation continuation,
        BaseFunction function,
        FuncallExpression caller,
        Frame lexicalFrame,
        Frame globalFrame,
        Set<String> knownGlobalVariables) {
      this.continuation = continuation;
      this.function = function;
      this.caller = caller;
      this.lexicalFrame = lexicalFrame;
      this.globalFrame = globalFrame;
      this.knownGlobalVariables = knownGlobalVariables;
    }
  }

  // TODO(bazel-team): Eliminate this hack around Java serialization. The bindings are currently
  // factored out into BaseExtension, which is non-Serializable, and which has a default constructor
  // that does not initialize any bindings. This means that when Extension is Java-serialized, all
  // the bindings are simply lost.
  private static class BaseExtension {

    protected final ImmutableMap<String, Object> bindings;

    BaseExtension(Map<String, Object> bindings) {
      this.bindings = ImmutableMap.copyOf(bindings);
    }

    // Hack to "allow" java serialization.
    BaseExtension() {
      this.bindings = ImmutableMap.of();
    }
  }

  /** An Extension to be imported with load() into a BUILD or .bzl file. */
  @Immutable
  public static final class Extension extends BaseExtension implements Serializable {

    /**
     * Cached hash code for the transitive content of this {@code Extension} and its dependencies.
     */
    private final String transitiveContentHashCode;

    /**
     * Constructs with the given hash code and bindings.
     */
    public Extension(Map<String, Object> bindings, String transitiveContentHashCode) {
      super(bindings);
      this.transitiveContentHashCode = transitiveContentHashCode;
    }

    /**
     * Constructs using the bindings from the global definitions of the given {@link Environment},
     * and that {@code Environment}'s transitive hash code.
     */
    public Extension(Environment env) {
      super(env.globalFrame.bindings);
      this.transitiveContentHashCode = env.getTransitiveContentHashCode();
    }

    public String getTransitiveContentHashCode() {
      return transitiveContentHashCode;
    }

    public ImmutableMap<String, Object> getBindings() {
      return bindings;
    }
  }

  /**
   * Static Frame for lexical variables that are always looked up in the current Environment
   * or for the definition Environment of the function currently being evaluated.
   */
  private Frame lexicalFrame;

  /**
   * Static Frame for global variables; either the current lexical Frame if evaluation is currently
   * happening at the global scope of a BUILD file, or the global Frame at the time of function
   * definition if evaluation is currently happening in the body of a function. Thus functions can
   * close over other functions defined in the same file.
   */
  private Frame globalFrame;

  /**
   * Dynamic Frame for variables that are always looked up in the runtime Environment,
   * and never in the lexical or "global" Environment as it was at the time of function definition.
   * For instance, PACKAGE_NAME.
   */
  private final Frame dynamicFrame;

  /**
   * The semantics options that affect how Skylark code is evaluated.
   */
  private final SkylarkSemanticsOptions semantics;

  /**
   * An EventHandler for errors and warnings. This is not used in the BUILD language,
   * however it might be used in Skylark code called from the BUILD language, so shouldn't be null.
   */
  private final EventHandler eventHandler;

  /**
   * For each imported extension, a global Skylark frame from which to load() individual bindings.
   */
  private final Map<String, Extension> importedExtensions;

  /**
   * Is this Environment being executed during the loading phase? Many builtin functions are only
   * enabled during the loading phase, and check this flag.
   * TODO(laurentlb): Remove from Environment
   */
  private final Phase phase;

  /**
   * When in a lexical (Skylark) Frame, this set contains the variable names that are global,
   * as determined not by global declarations (not currently supported),
   * but by previous lookups that ended being global or dynamic.
   * This is necessary because if in a function definition something
   * reads a global variable after which a local variable with the same name is assigned an
   * Exception needs to be thrown.
   */
  @Nullable private Set<String> knownGlobalVariables;

  /**
   * When in a lexical (Skylark) frame, this lists the names of the functions in the call stack.
   * We currently use it to artificially disable recursion.
   */
  @Nullable private Continuation continuation;

  /**
   * Gets the label of the BUILD file that is using this environment. For example, if a target
   * //foo has a dependency on //bar which is a Skylark rule defined in //rules:my_rule.bzl being
   * evaluated in this environment, then this would return //foo.
   */
  @Nullable private final Label callerLabel;

  /**
   * Enters a scope by saving state to a new Continuation
   * @param function the function whose scope to enter
   * @param caller the source AST node for the caller
   * @param globals the global Frame that this function closes over from its definition Environment
   */
  void enterScope(BaseFunction function, FuncallExpression caller, Frame globals) {
    continuation =
        new Continuation(
            continuation, function, caller, lexicalFrame, globalFrame, knownGlobalVariables);
    // TODO(bazel-team): What if instead of tracking both the lexical and global frames from the
    // Environment, we instead just tracked the current lexical frame, and made the global frame its
    // parent?
    lexicalFrame = new Frame(mutability(), null);
    globalFrame = globals;
    knownGlobalVariables = new HashSet<>();
  }

  /**
   * Exits a scope by restoring state from the current continuation
   */
  void exitScope() {
    Preconditions.checkNotNull(continuation);
    lexicalFrame = continuation.lexicalFrame;
    globalFrame = continuation.globalFrame;
    knownGlobalVariables = continuation.knownGlobalVariables;
    continuation = continuation.continuation;
  }

  private final String transitiveHashCode;

  /**
   * Checks that the current Environment is in the loading or the workspace phase.
   * TODO(laurentlb): Move to SkylarkUtils
   *
   * @param symbol name of the function being only authorized thus.
   */
  public void checkLoadingOrWorkspacePhase(String symbol, Location loc) throws EvalException {
    if (phase == Phase.ANALYSIS) {
      throw new EvalException(loc, symbol + "() cannot be called during the analysis phase");
    }
  }

  /**
   * Checks that the current Environment is in the loading phase.
   * TODO(laurentlb): Move to SkylarkUtils
   *
   * @param symbol name of the function being only authorized thus.
   */
  public void checkLoadingPhase(String symbol, Location loc) throws EvalException {
    if (phase != Phase.LOADING) {
      throw new EvalException(loc, symbol + "() can only be called during the loading phase");
    }
  }

  /**
   * Is this a global Environment?
   * @return true if the current code is being executed at the top-level,
   * as opposed to inside the body of a function.
   */
  boolean isGlobal() {
    return lexicalFrame == null;
  }

  @Override
  public Mutability mutability() {
    // the mutability of the environment is that of its dynamic frame.
    return dynamicFrame.mutability();
  }

  /** @return the current Frame, in which variable side-effects happen. */
  private Frame currentFrame() {
    return isGlobal() ? globalFrame : lexicalFrame;
  }

  /**
   * @return the global variables for the Environment (not including dynamic bindings).
   */
  public Frame getGlobals() {
    return globalFrame;
  }

  /**
   * Returns an EventHandler for errors and warnings.
   * The BUILD language doesn't use it directly, but can call Skylark code that does use it.
   * @return an EventHandler
   */
  public EventHandler getEventHandler() {
    return eventHandler;
  }

  /** @return the current stack trace as a list of functions. */
  ImmutableList<BaseFunction> getStackTrace() {
    ImmutableList.Builder<BaseFunction> builder = new ImmutableList.Builder<>();
    for (Continuation k = continuation; k != null; k = k.continuation) {
      builder.add(k.function);
    }
    return builder.build().reverse();
  }


  /**
   * Returns the FuncallExpression and the BaseFunction for the top-level call being evaluated.
   */
  public Pair<FuncallExpression, BaseFunction> getTopCall() {
    Continuation continuation = this.continuation;
    if (continuation == null) {
      return null;
    }
    while (continuation.continuation != null) {
      continuation = continuation.continuation;
    }
    return new Pair<>(continuation.caller, continuation.function);
  }

  /**
   * Constructs an Environment. This is the main, most basic constructor.
   *
   * @param globalFrame a frame for the global Environment
   * @param dynamicFrame a frame for the dynamic Environment
   * @param eventHandler an EventHandler for warnings, errors, etc
   * @param importedExtensions Extension-s from which to import bindings with load()
   * @param fileContentHashCode a hash for the source file being evaluated, if any
   * @param phase the current phase
   * @param callerLabel the label this environment came from
   */
  private Environment(
      Frame globalFrame,
      Frame dynamicFrame,
      SkylarkSemanticsOptions semantics,
      EventHandler eventHandler,
      Map<String, Extension> importedExtensions,
      @Nullable String fileContentHashCode,
      Phase phase,
      @Nullable Label callerLabel) {
    this.globalFrame = Preconditions.checkNotNull(globalFrame);
    this.dynamicFrame = Preconditions.checkNotNull(dynamicFrame);
    Preconditions.checkArgument(!globalFrame.mutability().isFrozen());
    Preconditions.checkArgument(!dynamicFrame.mutability().isFrozen());
    this.semantics = semantics;
    this.eventHandler = eventHandler;
    this.importedExtensions = importedExtensions;
    this.phase = phase;
    this.callerLabel = callerLabel;
    this.transitiveHashCode =
        computeTransitiveContentHashCode(fileContentHashCode, importedExtensions);
  }

  /**
   * A Builder class for Environment
   */
  public static class Builder {
    private final Mutability mutability;
    private Phase phase = Phase.ANALYSIS;
    @Nullable private Frame parent;
    @Nullable private SkylarkSemanticsOptions semantics;
    @Nullable private EventHandler eventHandler;
    @Nullable private Map<String, Extension> importedExtensions;
    @Nullable private String fileContentHashCode;
    private Label label;

    Builder(Mutability mutability) {
      this.mutability = mutability;
    }

    /**
     * Obsolete, doesn't do anything.
     * TODO(laurentlb): To be removed once call-sites have been updated
     */
    public Builder setSkylark() {
      return this;
    }

    /** Enables loading or workspace phase only functions in this Environment. */
    public Builder setPhase(Phase phase) {
      Preconditions.checkState(this.phase == Phase.ANALYSIS);
      this.phase = phase;
      return this;
    }

    /** Inherits global bindings from the given parent Frame. */
    public Builder setGlobals(Frame parent) {
      Preconditions.checkState(this.parent == null);
      this.parent = parent;
      return this;
    }

    public Builder setSemantics(SkylarkSemanticsOptions semantics) {
      this.semantics = semantics;
      return this;
    }

    /** Sets an EventHandler for errors and warnings. */
    public Builder setEventHandler(EventHandler eventHandler) {
      Preconditions.checkState(this.eventHandler == null);
      this.eventHandler = eventHandler;
      return this;
    }

    /** Declares imported extensions for load() statements. */
    public Builder setImportedExtensions (Map<String, Extension> importMap) {
      Preconditions.checkState(this.importedExtensions == null);
      this.importedExtensions = importMap;
      return this;
    }

    /** Declares content hash for the source file for this Environment. */
    public Builder setFileContentHashCode(String fileContentHashCode) {
      this.fileContentHashCode = fileContentHashCode;
      return this;
    }

    /** Builds the Environment. */
    public Environment build() {
      Preconditions.checkArgument(!mutability.isFrozen());
      if (parent != null) {
        Preconditions.checkArgument(parent.mutability().isFrozen());
      }
      Frame globalFrame = new Frame(mutability, parent);
      Frame dynamicFrame = new Frame(mutability, null);
      if (semantics == null) {
        semantics = Options.getDefaults(SkylarkSemanticsOptions.class);
      }
      if (importedExtensions == null) {
        importedExtensions = ImmutableMap.of();
      }
      return new Environment(
          globalFrame,
          dynamicFrame,
          semantics,
          eventHandler,
          importedExtensions,
          fileContentHashCode,
          phase,
          label);
    }

    public Builder setCallerLabel(Label label) {
      this.label = label;
      return this;
    }
  }

  public static Builder builder(Mutability mutability) {
    return new Builder(mutability);
  }

  /**
   * Returns the caller's label.
   */
  public Label getCallerLabel() {
    return callerLabel;
  }

  /**
   * Sets a binding for a special dynamic variable in this Environment.
   * This is not for end-users, and will throw an AssertionError in case of conflict.
   * @param varname the name of the dynamic variable to be bound
   * @param value a value to bind to the variable
   * @return this Environment, in fluid style
   */
  public Environment setupDynamic(String varname, Object value) {
    if (dynamicFrame.get(varname) != null) {
      throw new AssertionError(
          String.format("Trying to bind dynamic variable '%s' but it is already bound",
              varname));
    }
    if (lexicalFrame != null && lexicalFrame.get(varname) != null) {
      throw new AssertionError(
          String.format("Trying to bind dynamic variable '%s' but it is already bound lexically",
              varname));
    }
    if (globalFrame.get(varname) != null) {
      throw new AssertionError(
          String.format("Trying to bind dynamic variable '%s' but it is already bound globally",
              varname));
    }
    try {
      dynamicFrame.put(this, varname, value);
    } catch (MutabilityException e) {
      // End users don't have access to setupDynamic, and it is an implementation error
      // if we encounter a mutability exception.
      throw new AssertionError(
          String.format(
              "Trying to bind dynamic variable '%s' in frozen environment %s", varname, this),
          e);
    }
    return this;
  }

  /** Remove variable from local bindings. */
  void removeLocalBinding(String varname) {
    try {
      currentFrame().remove(this, varname);
    } catch (MutabilityException e) {
      throw new AssertionError(e);
    }
  }

  /**
   * Modifies a binding in the current Frame of this Environment, as would an
   * {@link AssignmentStatement}. Does not try to modify an inherited binding.
   * This will shadow any inherited binding, which may be an error
   * that you want to guard against before calling this function.
   * @param varname the name of the variable to be bound
   * @param value the value to bind to the variable
   * @return this Environment, in fluid style
   */
  public Environment update(String varname, Object value) throws EvalException {
    Preconditions.checkNotNull(value, "update(value == null)");
    // prevents clashes between static and dynamic variables.
    if (dynamicFrame.get(varname) != null) {
      throw new EvalException(
          null, String.format("Trying to update special read-only global variable '%s'", varname));
    }
    if (isKnownGlobalVariable(varname)) {
      throw new EvalException(
          null, String.format("Trying to update read-only global variable '%s'", varname));
    }
    try {
      currentFrame().put(this, varname, Preconditions.checkNotNull(value));
    } catch (MutabilityException e) {
      // Note that since at this time we don't accept the global keyword, and don't have closures,
      // end users should never be able to mutate a frozen Environment, and a MutabilityException
      // is therefore a failed assertion for Bazel. However, it is possible to shadow a binding
      // imported from a parent Environment by updating the current Environment, which will not
      // trigger a MutabilityException.
      throw new AssertionError(
          Printer.format("Can't update %s to %r in frozen environment", varname, value),
          e);
    }
    return this;
  }

  public boolean hasVariable(String varname) {
    return lookup(varname) != null;
  }

  /**
   * Initializes a binding in this Environment. It is an error if the variable is already bound.
   * This is not for end-users, and will throw an AssertionError in case of conflict.
   * @param varname the name of the variable to be bound
   * @param value the value to bind to the variable
   * @return this Environment, in fluid style
   */
  public Environment setup(String varname, Object value) {
    if (hasVariable(varname)) {
      throw new AssertionError(String.format("variable '%s' already bound", varname));
    }
    return setupOverride(varname, value);
  }

  /**
   * Initializes a binding in this environment. Overrides any previous binding.
   * This is not for end-users, and will throw an AssertionError in case of conflict.
   * @param varname the name of the variable to be bound
   * @param value the value to bind to the variable
   * @return this Environment, in fluid style
   */
  public Environment setupOverride(String varname, Object value) {
    try {
      return update(varname, value);
    } catch (EvalException ee) {
      throw new AssertionError(ee);
    }
  }

  /**
   * @return the value from the environment whose name is "varname" if it exists, otherwise null.
   */
  public Object lookup(String varname) {
    // Lexical frame takes precedence, then globals, then dynamics.
    if (lexicalFrame != null) {
      Object lexicalValue = lexicalFrame.get(varname);
      if (lexicalValue != null) {
        return lexicalValue;
      }
    }
    Object globalValue = globalFrame.get(varname);
    Object dynamicValue = dynamicFrame.get(varname);
    if (globalValue == null && dynamicValue == null) {
      return null;
    }
    if (knownGlobalVariables != null) {
      knownGlobalVariables.add(varname);
    }
    if (globalValue != null) {
      return globalValue;
    }
    return dynamicValue;
  }

  /**
   * @return true if varname is a known global variable,
   * because it has been read in the context of the current function.
   */
  boolean isKnownGlobalVariable(String varname) {
    return knownGlobalVariables != null && knownGlobalVariables.contains(varname);
  }

  public SkylarkSemanticsOptions getSemantics() {
    return semantics;
  }

  public void handleEvent(Event event) {
    eventHandler.handle(event);
  }

  /** Returns a set of all names of variables that are accessible in this {@code Environment}. */
  public Set<String> getVariableNames() {
    Set<String> vars = new HashSet<>();
    if (lexicalFrame != null) {
      vars.addAll(lexicalFrame.getTransitiveBindings().keySet());
    }
    vars.addAll(globalFrame.getTransitiveBindings().keySet());
    vars.addAll(dynamicFrame.getTransitiveBindings().keySet());
    return vars;
  }

  @Override
  public int hashCode() {
    throw new UnsupportedOperationException(); // avoid nondeterminism
  }

  @Override
  public boolean equals(Object that) {
    throw new UnsupportedOperationException();
  }

  @Override
  public String toString() {
    return String.format("<Environment%s>", mutability());
  }

  /**
   * An Exception thrown when an attempt is made to import a symbol from a file
   * that was not properly loaded.
   */
  static class LoadFailedException extends Exception {
    LoadFailedException(String importString) {
      super(String.format("file '%s' was not correctly loaded. "
              + "Make sure the 'load' statement appears in the global scope in your file",
          importString));
    }

    LoadFailedException(String importString, String symbolString, Iterable<String> allKeys) {
      super(
          String.format(
              "file '%s' does not contain symbol '%s'%s",
              importString, symbolString, SpellChecker.didYouMean(symbolString, allKeys)));
    }
  }

  void importSymbol(String importString, Identifier symbol, String nameInLoadedFile)
      throws LoadFailedException {
    Preconditions.checkState(isGlobal()); // loading is only allowed at global scope.

    if (!importedExtensions.containsKey(importString)) {
      throw new LoadFailedException(importString);
    }

    Extension ext = importedExtensions.get(importString);

    Map<String, Object> bindings = ext.getBindings();
    if (!bindings.containsKey(nameInLoadedFile)) {
      throw new LoadFailedException(importString, nameInLoadedFile, bindings.keySet());
    }

    Object value = bindings.get(nameInLoadedFile);

    try {
      update(symbol.getName(), value);
    } catch (EvalException e) {
      throw new LoadFailedException(importString);
    }
  }

  private static String computeTransitiveContentHashCode(
      @Nullable String baseHashCode, Map<String, Extension> importedExtensions) {
    // Calculate a new hash from the hash of the loaded Extension-s.
    Fingerprint fingerprint = new Fingerprint();
    if (baseHashCode != null) {
      fingerprint.addString(Preconditions.checkNotNull(baseHashCode));
    }
    TreeSet<String> importStrings = new TreeSet<>(importedExtensions.keySet());
    for (String importString : importStrings) {
      fingerprint.addString(importedExtensions.get(importString).getTransitiveContentHashCode());
    }
    return fingerprint.hexDigestAndReset();
  }

  /**
   * Returns a hash code calculated from the hash code of this Environment and the
   * transitive closure of other Environments it loads.
   */
  public String getTransitiveContentHashCode() {
    return transitiveHashCode;
  }

  /** A read-only Environment.Frame with global constants in it only */
  static final Frame CONSTANTS_ONLY = createConstantsGlobals();

  /** A read-only Environment.Frame with initial globals */
  public static final Frame DEFAULT_GLOBALS = createDefaultGlobals();

  /** To be removed when all call-sites are updated. */
  public static final Frame SKYLARK = DEFAULT_GLOBALS;

  private static Environment.Frame createConstantsGlobals() {
    try (Mutability mutability = Mutability.create("CONSTANTS")) {
      Environment env = Environment.builder(mutability).build();
      Runtime.setupConstants(env);
      return env.getGlobals();
    }
  }

  private static Environment.Frame createDefaultGlobals() {
    try (Mutability mutability = Mutability.create("BUILD")) {
      Environment env = Environment.builder(mutability).build();
      Runtime.setupConstants(env);
      Runtime.setupMethodEnvironment(env, MethodLibrary.defaultGlobalFunctions);
      return env.getGlobals();
    }
  }

  /** An exception thrown by {@link #FAIL_FAST_HANDLER}. */
  // TODO(bazel-team): Possibly extend RuntimeException instead of IllegalArgumentException.
  public static class FailFastException extends IllegalArgumentException {
    public FailFastException(String s) {
      super(s);
    }
  }

  /**
   * A handler that immediately throws {@link FailFastException} whenever an error or warning
   * occurs.
   *
   * We do not reuse an existing unchecked exception type, because callers (e.g., test assertions)
   * need to be able to distinguish between organically occurring exceptions and exceptions thrown
   * by this handler.
   */
  public static final EventHandler FAIL_FAST_HANDLER = new EventHandler() {
    @Override
    public void handle(Event event) {
      if (EventKind.ERRORS_AND_WARNINGS.contains(event.getKind())) {
        throw new FailFastException(event.toString());
      }
    }
  };
}