Add support to manually freeze mutable values in starlark

[matts1]

There are a variety of reasons why one might want to freeze a value yourself. Here's one example - defining a foo and a foo_set rule, you can't have a mutable type in your foo rule and be able to use a foo as a foo_set.

FooInfo = provider(fields = {
    ...,
    "dict_value": "Dict[k, v]", 

FooSetInfo = provider(fields = {
    "foos": "depset[FooInfo]"
})

The following code is not considered valid:

def _foo_impl(ctx):
    foo = FooInfo(dict_value = {})
    return [foo, FooSetInfo(foos = depset([foo])]

However, the following code is considered valid:

def foo_set_impl(ctx):
    return FooSetInfo(foos = depset([
        target[FooInfo] for target in ctx.attr.foos
    ])

I propose adding a dict.freeze() and list.freeze() method (or .frozen(), if doing so creates a frozen copy instead of mutating the original value).

[stepancheg]

If proposed "freeze" deep? I.e. does it freeze the content or just create an immutable value, like Python's frozenset?

Also, to clarify, you only propose to freeze the lists and dicts, not arbitrary types?

[matts1]

I was reading the documentation, and it says "Two mutable data structures are available: lists and dicts.". This is why I only proposed to freeze those two types.

I hadn't really considered a deep freeze. If it's a deep freeze I guess freezing arbitrary types would be useful, since you could freeze struct(a={}), for example. It's probably a question of what's easiest to implement - a shallow freeze would probably be sufficient, but if a deep freeze is easier there's certainly no harm in doing so.

I think if it is a shallow freeze, a method is probably better than a function to ensure that it's only ever used on the correct type, but for a deep freeze, a function freeze would be the way to go.

[adonovan]

FWIW, the Go implementation of Starlark already supports this operator, which works by traversing the object graph, much like the mark phase of a garbage collector, setting a boolean field in each data structure. The Java implementation takes a different approach: as each mutable data structure is constructed, it records a pointer to a single shared boolean variable that belongs to the module; when the module initialization is complete, this variable is set to true and all the mutable data structures become immutable. The Go approach costs only one byte per structure, and permits a simpler API, but requires traversal logic; the Java approach requires one word per structure, and requires all constructors to take a pointer to the 'frozen' variable, but the logic is simpler.

What both implementations share in common is that frozen data cannot refer to unfrozen data, and this invariant is crucial for preventing data races. In other words the freeze operator absolutely must be "deep", not shallow.

[brandjon]

As Alan mentioned, the Java and Go implementations have drastically different strategies for tracking what values are frozen. Adding a per-value freeze() primitive is incompatible with the Java implementation, so we can't add it to the spec without carving out a big optional / implementation-dependent caveat, perhaps defeating the point.

See #64, which may impact the motivating example given above, depending on to what extent depsets can look the other way when they are given hashable but not-yet-frozen values. See also this code comment.

[brandjon]

For this issue though: Is there any real benefit to specifying a freeze() primitive that can't be implemented in all Starlark interpreters, and particularly not in Bazel?