[CAS] Add LLVMCAS library with InMemoryCAS implementation

[steven_wu]

Summary

Add llvm::cas::ObjectStore abstraction and InMemoryCAS as a in-memory
CAS object store implementation.

The ObjectStore models its objects as:

• Content: An array of bytes for the data to be stored.
• Refs: An array of references to other objects in the ObjectStore.

And each CAS Object can be idenfied with an unqine ID/Hash.

ObjectStore supports following general action:

• Expected<ID> store(Content, ArrayRef<Ref>)
• Expected<Ref> get(ID)

It also introduces following types to interact with a CAS ObjectStore:

• CASID: Hash representation for an CAS Objects with its context to help print/compare CASIDs.
• ObjectRef: A light-weight ref for an object in the ObjectStore. It is implementation defined so it can be optimized for read/store/references depending on the implementation.
• ObjectHandle: A CAS internal light-weight handle to an loaded object in the ObjectStore. Underlying data for the object is guaranteed to be available and no error handling is required to access data. This is not exposed to the users of CAS from ObjectStore APIs.
• ObjectProxy: A proxy for the users of CAS to interact with the data inside CAS Object. It bundles a ObjectHandle and an ObjectStore instance.

[steven_wu]

Ping.

Now with context of the LLVM talk, I hope it makes the review easier. Will be really appreciated for any feedback to get CAS upstream. Feel free to reach out to me for any questions.

[dexonsmith]

In D133716#3958319, @steven_wu wrote:

Ping.

Now with context of the LLVM talk, I hope it makes the review easier. Will be really appreciated for any feedback to get CAS upstream. Feel free to reach out to me for any questions.

FTR, I'll be happy to review most/many patches in this area once the core patches land (and also contribute to design discussions), but for the core patches (where I was the original author) I'm not sure I have enough perspective to spot what's missing. As such, I'm going to resign as a reviewer, but I'll still be "subscribed" to the email thread. (Feel free to add me as a subscriber/reviewer to anything else in this area as well...)

In my opinion, much of this can evolve in-tree after landing, and the RFC had consensus to move forward with landing this stuff in main following the usual code review. It's important for someone outside the original authors (a few Apple people, plus me!) to at least take a cursory look to ensure that it's well-enough documented and tested for others to contribute. Maybe an in-depth review isn't needed, but I'm sure that'd also be welcome if someone can contribute one.

Alternatively, if someone thinks the design needs a deeper look before landing, that sounds great too; but I think it'd be helpful for Steven to have signal either way.

+@MatzeB, in case you are able to contribute a review; IIRC, it was your design feedback in the RFC video call that caused us to simplify the interface, moving filesystem concepts like "blobs" and "trees" out of the core CAS interface.

[dexonsmith]

llvm/include/llvm/ADT/StringExtras.h

61–74 ↗

(On Diff #459516)

Oh, just noticed these changes; I suggest separating these out and adding quick unit tests.

[steven_wu]

Split StringExtras changes

[dblaikie]

llvm/include/llvm/CAS/CASID.h

26

This could be private to avoid polluting autocomplete and such, maybe? (alternatively it's probably not too costly to have the dtor virtual and out of line to act as an anchor - I assume CASContexts aren't being created/torn down with any great frequency such that some dtor indirection would be especially costly?)

108–109

if you have a std::string member, should probably take the parameter as std::string and std::move it into the member - in cases where the caller can discard a string that'll be more efficient, and in cases where the caller can't, it's not especially worse.

(though shoudl the member be std::string? should it be SmallString or anything else?)

llvm/include/llvm/CAS/CASReference.h

62

Only the last of these checks is limited to LLVM_ENABLE_ABI_BREAKING_CHECKS yeah? Might be worth pulling the other two out of the preprocessor conditional, so they get run more broadly?

106

expect -> extract? or something else?

110–113

If clients aren't expected to need to do it, could we leave that out until some necessary use comes up?

162

Since Handle and Ref aren't especially self documenting (while reading the docs for Ref I wondered if it should be called Handle - until I got to the bit where it explained that that exists too/separately) - is there something that'd be more explicit about the difference between these? (like, I wonder if ObjectHandle could be Object? - not sure that'd make ObjectRef more obvious, though... )

llvm/include/llvm/CAS/ObjectStore.h

49

do they "reference" other objects - or does an object consist of other objects/include those objects in some sense? (maybe there's no real difference, and this current language is better... not sure)

53–57

Not clear from this what the difference between an ObjectRef and a CASID are - is that worth more details?

61–64

Ah. May be worth splitting up the documentation here more clearly between public and private concepts, rather than having this internal detail interleaved with external ones?

90

anchor's only useful if it's virtual?
Maybe jus tmake the dtor out of line and use that as an anchor?

109–110

what sort of validity is of concern here?

174–175

this lets you walk which other objects reference this object?
I guess you've probably got some pretty core use cases/need for this - but dealing with updating use lists in LLVM IR at least makes me ask: Do you need to be able to walk the uses of an object?

llvm/lib/CAS/InMemoryCAS.cpp

262

I'd probably put the inline keyword here and leave it off the declaration (otherwise I'd read this code and wonder how it's valid/doesn't produce duplicate definitions) - wonder what's more common in the LLVM project/codebase. No big deal either way, though.

llvm/unittests/CAS/ObjectStoreTest.cpp

161

not sure I understand the mention of std::string here - since this is StringRef? (maybe this is some remnant of a different version of the code)

173–175

Rather than testing this via UB, could it be tested via pointer equality? (eg: when querying the CAS, check that the data points to the same place as the data pasesd in)

[steven_wu]

Address review feedback.

[steven_wu]

@dblaikie Thanks for reviewing. Feedback inline.

llvm/include/llvm/CAS/CASID.h

26

This is a private method? But sure this is not a common object to create or destory. dtor as anchor sounds fine.

108–109

I don't have much preference for the internal data type. CASID should only be relevant when you actually need the hash representation, often when you need to print out the value for outside users. Otherwise, ObjectRef is always a better choice.

llvm/include/llvm/CAS/CASReference.h

106

This comment is out-dated. The builtin kind of the object is removed from the latest implementation to simplify the interface so it is easier to use and implement

110–113

It actually means that only the CAS implementers should use those method (for example, used in BuiltinCAS) but users of the CAS should not use those methods because InternalRef has no meaning outside the CAS internal. I rewrite it to clear up a bit.

162

ObjectRef is just a reference, and you can't access anything in the object it points to, until you load the object using ObjectRef, which will turn into an ObjectHandle. The load can have latency or can fail.

Maybe the comments in ObjectStore.h is a better explanation with a bigger picture? Or should we put all the documentation into one place so it is easier to read?

llvm/include/llvm/CAS/ObjectStore.h

49

It is a real reference, like a pointer reference. But this is up to the CAS implementation, as I can see it is totally possible to implement a CAS the directly embeds the "referenced" object without breaking the contract of the API, but there is really no good reason to do that.

53–57

I refine the docs a bit. Let me know if it is clearer to read.

109–110

This is more a debugging function that can check if the integrity of the CAS has been broken. The current implementation for builtin CAS is to rehash the object fetched from CASID and make sure the hash matches. If not, there is either a bug in CAS or the data has been corrupted.

174–175

No, the reference in CAS goes only one direction. This iterates through all the objects that is referenced by the current object and you don't know how many parents references you.

In general, there is even no API for CAS to iterate through all the objects to compute a use-list and that is by design.

[steven_wu]

Cleanup patch to move unrelated changes.

[dblaikie]

llvm/include/llvm/CAS/CASID.h

108–109

Cool - I see you updated the parameter to std::string&& - generally I'd expect it to be std::string value, not a reference. That way the caller can move into the parameter if they have a string to discard, or allow the copy if they want to keep copies in the caller for whatever reason.

llvm/include/llvm/CAS/CASReference.h

162

Still feels like the names could be more self-descriptive, even with/independent of documentation improvements. Ref and Handle both tend to connote a thing you can use to inspect the thing being referred to or handled. (if anything, I guess I'd actually expect a Handle to be the inaccessible version and the Ref to be the accessible version (thinking StringRef, ArrayRef, etc - where the data is directly accessible through that abstraction, whereas handles sometimes you have to pass back into some other object/API to then get the data (like a file handle/file descriptor)))

Seems like ObjectRef is maybe more suitably called ObjectID?

llvm/include/llvm/CAS/ObjectStore.h

60

Presumably it can also fail if the object isn't in the given CAS? (maybe that's the more obvious/simpler to document example?)

61–64

ping on this

109–110

Might be worth a few more words in the description maybe about "consistency" or somesuch?

[steven_wu]

llvm/include/llvm/CAS/CASReference.h

162

I don't have strong opinion on names. Maybe @dexonsmith @benlangmuir @akyrtzi can also provide some feedbacks for names?

In my opinion, ObjectRef is named that way because it is like a reference type (just an opaque pointer) and you need to "dereference" it to access underlying data, just that the dereference might fail in CAS. The difference between ObjectRef and ObjectHandle is mostly providing the flexibility for a remote CAS so there is no need to traffic all the data if you only dealing with refs.

Also ObjectRef is the public type we encourage to use, just like other Ref types like StringRef and ArrayRef. It is cheap and allows quick fetch of the underlying data (at least for the builtin CAS we provided). It doesn't really contains ID, and you can't compare Ref from different ObjectStore.

I thought about rename CASID to ObjectID to keep the name consistent, but there is no other more benefit. I am up for renaming types to make it more self-descriptive but I would like to reach an agreement before doing so because we have lots of downstream code needs to upstream and I would like to avoid repeated renames.

llvm/include/llvm/CAS/ObjectStore.h

60

This question is complicated. Maybe we should write down a spec for the CAS APIs? To this question, the current spec for when to lookup for a CAS object to make sure it exists is totally implementation defined.

For builtinCAS here, ObjectRef always points to existing object, unless the integrity of the builtinCAS is broken. For a remote CAS, you might actually want to have ObjectRef to be unverified to avoid a roundtrip to remote to validate a ObjectRef.

Also to you previous point of split up public/private interface document, is it better if I create a separate docs in llvm/docs to explain different concepts from the views of: 1. CAS users 2. CAS implementors?

[benlangmuir]

llvm/include/llvm/CAS/CASReference.h

162

I agree with Steven; I think ObjectRef deserves the good name here, since that's the one that clients of an ObjectStore will work with. ObjectHandle is only used by implementors of an ObjectStore. I agree that having both Ref and Handle is confusing - maybe we should rename Handle to something more verbose and descriptive like LoadedObjectRef.

Seems like ObjectRef is maybe more suitably called ObjectID?

I think this is confusing with CASID, which really is an ID. I don't have a strong opinion on whether CASID should be renamed to ObjectID or not for consistency.

[benlangmuir]

llvm/include/llvm/CAS/ObjectStore.h

60

This question is complicated. Maybe we should write down a spec for the CAS APIs? To this question, the current spec for when to lookup for a CAS object to make sure it exists is totally implementation defined

This complication is only for the implementation though, right? Clients of the object store shouldn't assume the object exists in the CAS, and like @dblaikie said, loading can fail if it is not. I don't think we want to promise that builtin CAS will always succeed when loading, since we might want to change that kind of detail later.

[dexonsmith]

llvm/include/llvm/CAS/CASReference.h

162

In my mind, the name ObjectID was "taken", since I originally thought we'd do a s/CASID/ObjectID/g at some point (maybe this patch / before upstreaming is the right time?). Maybe it would be even better to do s/CASID/std::string/.

(Historical note: an earlier design had neither ObjectRef nor ObjectHandle, just CASID. CASIDs were tied to a specific CAS instance, had odd lifetimes, and tried to serve all three purposes. We figured out that this was awkward, especially for distributed/remote CAS implementations.)

ObjectRef is a reference to an object (possibly an ID, possible some internal CAS pointer). As @steven_wu points out, having an ObjectRef doesn't necessarily mean you know anything about the content of an object.

ObjectHandle promises that you can access the object.

I think to explain the difference, it helps to have a specific example. If you have a few objects:

object-id: 0
data: "some small data"

object-id: 1
data: [4GB of data]

object-id: 2
data: "a header"
refs: 0, 1

If you have an ObjectHandle for object 2, then you can see that the data is "a header" and you can get the ObjectRefs for the objects it references: 0 and 1.

Those ObjectRefs allow you to talk about objects 0 and 1 without necessarily loading / downloading them, which is important because object 1 is 4GB big. You can create a new object that references them, and you can get a serialized reference (CASID/ObjectID/std::string) for referring to it in other contexts.

Or, you can "load" an ObjectRef, get an ObjectHandle for that object, and look at its content/refs. If you have a distributed CAS, or the object is big, or [etc.], this action might have significant latency. I imagine we'd eventually want to add an API to allow asynchronous loading.

It's a good point that "ref" here bears no relation to the "ref" in ArrayRef. That makes it confusing. It is identifier-like, even if it doesn't know how to serialize itself into a string (you need the CAS instance to string-ify it for you).

At a high level, we have three concepts:

• a serialized, context-free identifier (currently CASID)
• an opaque, context-sensitive reference to an object known to "exist somewhere" (currently ObjectRef)
• a context-sensitive reference to an object known to "be local/loaded" (currently ObjectHandle)

Maybe the following rename could work:

1. Delete CASID and replace its usage with std::string
2. Rename ObjectRef to ObjectID
3. Maybe: Rename ObjectHandle to ObjectRef

I don't have a strong opinion about whether that results in a better world. The "current" names are kind of etched into my brain so it's hard to evaluate.

@steven_wu and @benlangmuir, WDYT? Is there something I'm missing/forgetting that makes this a bad idea?

@dblaikie, WDYT? Maybe you have other name ideas after the above explanation?

[dexonsmith]

llvm/include/llvm/CAS/CASReference.h

162

@benlangmuir, just seeing your reply. I'd have expected clients to work with both ObjectRef and ObjectHandle; but you have much more experience than I do. (I guess the ObjectHandle is only indirectly useful to clients. For any serious work, you want to create a proxy that wraps an ObjectHandle and navigates the content in a structured way.)

Agreed that ObjectRef ought to have a good / easy-to-type name.

[steven_wu]

llvm/include/llvm/CAS/CASReference.h

162

@dexonsmith Correct, we clean up the interface that no public methods from ObjectStore return ObjectHandle anymore so users access data in object through ObjectProxy. One less data type to deal with for CAS users and ObjectProxy has slightly better interfaces to type as well.

ObjectHandle is type for CAS implementor only now to represent loaded object.

llvm/include/llvm/CAS/ObjectStore.h

60

True. I will update the wording.

[akyrtzi]

llvm/include/llvm/CAS/CASReference.h

162

I'd have expected clients to work with both ObjectRef and ObjectHandle

I don't think ObjectHandle has any value for clients, clients will be using ObjectProxy.

an opaque, context-sensitive reference to an object known to "exist somewhere" (currently ObjectRef)

Something to highlight about this: For a "remote CAS" implementation you practically don't know that "an object is known to exist" until you try to load it. From that respect there is essentially no functional difference between CASID and ObjectRef in such a context.

[dexonsmith]

llvm/include/llvm/CAS/CASReference.h

162

Ah, that sounds great (I apologize for not reading the patch itself). Agreed with @benlangmuir that LoadedObjectHandle seems pretty reasonable if clients never have to use it.

Does my understanding the roles still stand? (Maybe that example could/should be used somewhere in the docs to clarify.)

Also:

• Do we still need CASID? Why not just use std::string?
• If we don't need CASID and can delete it, WDYT of renaming ObjectRef to ObjectID? (It could be thought of as an "opaque" identifier.)
• Another idea: rename ObjectRef to ObjectPtr?

[dexonsmith]

llvm/include/llvm/CAS/CASReference.h

162

Something to highlight about this: For a "remote CAS" implementation you practically don't know that "an object is known to exist" until you try to load it. From that respect there is essentially no functional difference between CASID and ObjectRef in such a context.

Ah, is that because a remote CAS may have garbage-collected the object? So, then, ObjectRef is just an object we know how to point at?

(Or do you just mean that loading could fail because the remote CAS goes down?)

[benlangmuir]

llvm/include/llvm/CAS/CASReference.h

162

Ah, is that because a remote CAS may have garbage-collected the object? So, then, ObjectRef is just an object we know how to point at?
(Or do you just mean that loading could fail because the remote CAS goes down?)

We do not check whether an object exists at all when creating the ObjectRef for a remote CAS: it's a wasted round trip over the network since you can't guarantee the object still exists later, and don't get a performance win for knowing it existed in the past. This is different with the local in-memory and on-disk CASes, because they can check for existence cheaply and provide a faster ref implementation once we know the object exists.

• a serialized, context-free identifier (currently CASID)

There are two levels here:

• a serialized, context-free identifier (std::string, e.g. "llvmcas://<serialized hash>")
• a context-sensitive identifier hash containing raw hash bytes (CASID) -- you need a CASContext to use it

an opaque, context-sensitive reference to an object known to "exist somewhere" (currently ObjectRef)

Not known to exist anywhere, but otherwise yes.

a context-sensitive reference to an object known to "be local/loaded" (currently ObjectHandle)

Correct.

Also:

• Do we still need CASID? Why not just use std::string?

So the question here is whether CASID is pulling its weight as a client-visible type. It should be more efficient than the serialized string, since you have the hash bytes immediately available rather than parsing them out; it can be smaller for the same reason. I don't know if have measured this -- @steven_wu, @akyrtzi any thoughts?

• If we don't need CASID and can delete it, WDYT of renaming ObjectRef to ObjectID? (It could be thought of as an "opaque" identifier.)

If we can drop CASID, I'm fine with this.

• Another idea: rename ObjectRef to ObjectPtr?

I find Ref clearer than Ptr for what it does.

[akyrtzi]

llvm/include/llvm/CAS/CASReference.h

162

I like the idea of dropping CASID entirely. I'm also fine with renaming ObjectRef to ObjectID.
I would also suggest that we change

virtual Expected<ObjectHandle> load(ObjectRef Ref)

to

virtual Expected<Optional<ObjectHandle>> load(ObjectRef Ref)

The optional indicates whether the object existed or not, and we reserve errors for catastrophic failures (e.g. "network went down"). The client could choose to turn the "object doesn't exist" None into an error (or not, it depends on the context) but this case should be distinguishable from ObjectStore's API.

[steven_wu]

llvm/include/llvm/CAS/CASReference.h

162

I tried to get rid of CASID but there are some desirable features that decide to keep it for now. For example, it distinguishes itself from a printable string.

For builtinCAS, you have a printable string that is something like: llvmcas://abcdefg..., while CASID is the raw hash value (0xabcdefg...) + the context ("llvm.builtin.cas.v1[BLAKE3]"). If we get rid of CASID, you will either have a std::string representation that is llvmcas:// then you need to parse it every time you want access to raw hash, or you decide to have std::string to store the raw hash value, then: 1. you can't store a context anywhere. 2. It is confusing if a function is taking a printable string or a raw hash value, since both of them are std::string.

[akyrtzi]

llvm/include/llvm/CAS/CASReference.h

162

then you need to parse it every time you want access to raw hash

Why do I need to parse the string to get the raw hash, I should be able to get the raw hash from the ObjectRef/ObjectID, right?
Once I parse a "llvmcas://" string into an ObjectRef/ObjectID there should be no need to keep the string around anymore.

[dexonsmith]

llvm/include/llvm/CAS/CASReference.h

162

What is "every time"? I.e., why do you need to get the hash from the CASID? Could/should some/many places that currently use CASID use an ObjectRef instead?

IOW, maybe some current uses of CASID should switch to ObjectRef or ObjectProxy, and the rest can then be converted to std::string. But I'm not sure. Only asking the question to ensure that you've considered it (vs. momentum of code written with CASID before ObjectRef existed).

[dexonsmith]

llvm/include/llvm/CAS/CASReference.h

162

Paging in old memories, I think where CASID remains useful is if you're talking about the same object in two different instances of a CAS (maybe one instance is in-memory, and the other is on-disk or remote), and both have the same CASContext. IIRC, you share a CASContext iff the std::strings mean the same thing. E.g., should be true for any CAS that has a std::string ID starting with llvmcas://, as long as both instances use the same hash function (currently always BLAKE3, right?). (Unless this changed...)

If a client is doing a lot of this, having an optimized representation of the hash/identifier could be useful; it avoids repeatedly serializing/parsing/validating std::strings just to communicate a hash from one CAS instance to another. (In this scenario, it's also maybe nice to avoid a malloc/dealloc, but the hash will always overflow std::string's small storage... that was the motivation to avoid std::string originally.)

I imagine we'll want to do that sort of thing at some point, but not sure how urgent it is (maybe it's already needed?), or whether the optimization is really necessary (maybe the overhead is hidden by other things that are orders of magnitude more expensive?)...

Outside of that multi-CAS-instance-same-CAScontext scenario, I'm not sure I see a reason to avoid using ObjectRef (or std::string).

Another thought: if we don't drop CASID, it could be renamed to ObjectHash.

• ObjectHash: the raw hash of the object, shareable within a CASContext (né CASID)
• ObjectID: an opaque identifier for a specific CAS instance (né ObjectRef)
• LoadedObjectHandle: implementation detail, points at "loaded" object in a CAS instance (né ObjectHandle)
• ObjectProxy: LoadedObjectHandle+ObjectStore+nice APIs.

[akyrtzi]

llvm/include/llvm/CAS/CASReference.h

162

it avoids repeatedly serializing/parsing/validating std::strings just to communicate a hash from one CAS instance to another.

Hmm, it's still unclear to me why you need to traffic "llvmcas://" strings for that; the ObjectRef/ID that you got from one instance should be able to provide the hash bytes for the other. You don't need to re-validate the hash because the instances are context-compatible.

[dexonsmith]

llvm/include/llvm/CAS/CASReference.h

162

IIRC, CASID is the only container for the raw hash recognized by ObjectStore. If you take it away, and you want to traffic in raw hashes you need to invent a new container for them (or just let people use ArrayRef).

If you think it’s useful to traffic in raw hashes, then I suggest keeping CASID/ObjectHash, since it has some error checking and dumping built-in.

[akyrtzi]

llvm/include/llvm/CAS/CASReference.h

162

or just let people use ArrayRef

I'm personally fine with making it that the way you get an ObjectID is either via parsing a string identifier or via passing the ArrayRef hash bytes (for example, say I stored the hash as raw bytes in a file and now I want to get an ObjectID out of these bytes).

Like a string identifier from a command-line option, the raw hash bytes will be a transient input that I will use to get an ObjectID in order to proceed with the rest of the work, I shouldn't need to be "trafficking" both hash bytes and ObjectIDs, at the same time.

In general, as a client I'd like to have only 3 concepts that I need to be concerned about:

1. A string identifier for a CAS object that can be parsed and printed (e.g. the "llvmcas://" strings)
2. A type I can get as a valid ID after parsing a string identifier or after passing the hash bytes for the object (e.g. ObjectID)
3. A type that contains the loaded data for the object. (e.g. ObjectProxy)

An ObjectHash type could be useful for the implementations but I find it an unnecessary concept for the users of ObjectStore API.

[dexonsmith]

llvm/include/llvm/CAS/CASReference.h

162

Sure; encapsulation might be overkill. I don’t feel strongly!

[steven_wu]

Rebase for std::optional

[steven_wu]

Add docs in the reference page that address CAS in different prespective.

Still use old names before do a global rename to a better name.

[steven_wu]

Update patch after HashMap rename

[steven_wu]

Update after makeArrayRef depreciation.

[steven_wu]

Rebase patch

llvm/include/llvm/CAS/CASID.h

+//===- llvm/CAS/CASID.h -----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CAS_CASID_H
+#define LLVM_CAS_CASID_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace llvm {
+
+class raw_ostream;
+
+namespace cas {
+
+class CASID;
+
+/// Context for CAS identifiers.
+class CASContext {
+  virtual void anchor();
+
+public:
+  virtual ~CASContext() = default;
+
+  /// Get an identifer for the schema used by this CAS context. Two CAS
+  /// instances should return \c true for this identifier if and only if their
+  /// CASIDs are safe to compare by hash. This is used by \a
+  /// CASID::equalsImpl().
+  virtual StringRef getHashSchemaIdentifier() const = 0;
+
+protected:
+  /// Print \p ID to \p OS.
+  virtual void printIDImpl(raw_ostream &OS, const CASID &ID) const = 0;
+
+  friend class CASID;
+};
+
+/// Unique identifier for a CAS object.
+///
+/// Locally, stores an internal CAS identifier that's specific to a single CAS
+/// instance. It's guaranteed not to change across the view of that CAS, but
+/// might change between runs.
+///
+/// It also has \a CASIDContext pointer to allow comparison of these
+/// identifiers. If two CASIDs are from the same CASIDContext, they can be
+/// compared directly. If they are, then \a
+/// CASIDContext::getHashSchemaIdentifier() is compared to see if they can be
+/// compared by hash, in which case the result of \a getHash() is compared.
+class CASID {
+public:
+  void dump() const;
+  void print(raw_ostream &OS) const {
+    return getContext().printIDImpl(OS, *this);
+  }
+  friend raw_ostream &operator<<(raw_ostream &OS, const CASID &ID) {
+    ID.print(OS);
+    return OS;
+  }
+  std::string toString() const;
+
+  ArrayRef<uint8_t> getHash() const;
+
+  friend bool operator==(const CASID &LHS, const CASID &RHS) {
+    // EmptyKey or TombstoneKey.
+    if (!LHS.Context || !RHS.Context)
+      return false;
+
+    // CASIDs are equal when they have the same hash schema and same hash value.
+    return LHS.Context->getHashSchemaIdentifier() ==
+               RHS.Context->getHashSchemaIdentifier() &&
+           LHS.Hash == RHS.Hash;
+  }
+
+  friend bool operator!=(const CASID &LHS, const CASID &RHS) {
+    return !(LHS == RHS);
+  }
+
+  friend hash_code hash_value(const CASID &ID) {
+    ArrayRef<uint8_t> Hash = ID.getHash();
+    return hash_combine_range(Hash.begin(), Hash.end());
+  }
+
+  const CASContext &getContext() const {
+    assert(Context && "Tombstone or empty key for DenseMap?");
+    return *Context;
+  }
+
+  static CASID getDenseMapEmptyKey() {
+    return CASID(nullptr, DenseMapInfo<StringRef>::getEmptyKey());
+  }
+  static CASID getDenseMapTombstoneKey() {
+    return CASID(nullptr, DenseMapInfo<StringRef>::getTombstoneKey());
+  }
+
+  CASID() = delete;
+
+  static CASID create(const CASContext *Context, StringRef Hash) {
+    return CASID(Context, Hash);
+  }
+
+private:
+  CASID(const CASContext *Context, StringRef Hash)
+      : Context(Context), Hash(Hash) {}
+
+  const CASContext *Context;
+  std::string Hash;
+};
+
+} // namespace cas
+
+template <> struct DenseMapInfo<cas::CASID> {
+  static cas::CASID getEmptyKey() { return cas::CASID::getDenseMapEmptyKey(); }
+
+  static cas::CASID getTombstoneKey() {
+    return cas::CASID::getDenseMapTombstoneKey();
+  }
+
+  static unsigned getHashValue(cas::CASID ID) {
+    return (unsigned)hash_value(ID);
+  }
+
+  static bool isEqual(cas::CASID LHS, cas::CASID RHS) { return LHS == RHS; }
+};
+
+} // namespace llvm
+
+#endif // LLVM_CAS_CASID_H

llvm/include/llvm/CAS/CASReference.h

+//===- llvm/CAS/CASReference.h ----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CAS_CASREFERENCE_H
+#define LLVM_CAS_CASREFERENCE_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace llvm {
+
+class raw_ostream;
+
+namespace cas {
+
+class ObjectStore;
+
+class ObjectHandle;
+class ObjectRef;
+
+/// Base class for references to things in \a ObjectStore.
+class ReferenceBase {
+protected:
+  struct DenseMapEmptyTag {};
+  struct DenseMapTombstoneTag {};
+  static constexpr uint64_t getDenseMapEmptyRef() { return -1ULL; }
+  static constexpr uint64_t getDenseMapTombstoneRef() { return -2ULL; }
+
+public:
+  /// Get an internal reference.
+  uint64_t getInternalRef(const ObjectStore &ExpectedCAS) const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    assert(CAS == &ExpectedCAS && "Extracting reference for the wrong CAS");
+#endif
+    return InternalRef;
+  }
+
+  unsigned getDenseMapHash() const {
+    return (unsigned)llvm::hash_value(InternalRef);
+  }
+  bool isDenseMapEmpty() const { return InternalRef == getDenseMapEmptyRef(); }
+  bool isDenseMapTombstone() const {
+    return InternalRef == getDenseMapTombstoneRef();
+  }
+  bool isDenseMapSentinel() const {
+    return isDenseMapEmpty() || isDenseMapTombstone();
+  }
+
+protected:
+  void print(raw_ostream &OS, const ObjectHandle &This) const;
+  void print(raw_ostream &OS, const ObjectRef &This) const;
+
+  bool hasSameInternalRef(const ReferenceBase &RHS) const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    assert(
+        (isDenseMapSentinel() || RHS.isDenseMapSentinel() || CAS == RHS.CAS) &&
+        "Cannot compare across CAS instances");
+#endif
+    return InternalRef == RHS.InternalRef;
+  }
+
+protected:
+  friend class ObjectStore;
+  ReferenceBase(const ObjectStore *CAS, uint64_t InternalRef, bool IsHandle)
+      : InternalRef(InternalRef) {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    this->CAS = CAS;
+#endif
+    assert(InternalRef != getDenseMapEmptyRef() && "Reserved for DenseMapInfo");
+    assert(InternalRef != getDenseMapTombstoneRef() &&
+           "Reserved for DenseMapInfo");
+  }
+  explicit ReferenceBase(DenseMapEmptyTag)
+      : InternalRef(getDenseMapEmptyRef()) {}
+  explicit ReferenceBase(DenseMapTombstoneTag)
+      : InternalRef(getDenseMapTombstoneRef()) {}
+
+private:
+  uint64_t InternalRef;
+
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+  const ObjectStore *CAS = nullptr;
+#endif
+};
+
+/// Reference to an object in a \a ObjectStore instance.
+///
+/// If you have an ObjectRef, you know the object exists, and you can point at
+/// it from new nodes with \a ObjectStore::store(), but you don't know anything
+/// about it. "Loading" the object is a separate step that may not have
+/// happened yet, and which can fail (due to filesystem corruption) or
+/// introduce latency (if downloading from a remote store).
+///
+/// \a ObjectStore::store() takes a list of these, and these are returned by \a
+/// ObjectStore::forEachRef() and \a ObjectStore::readRef(), which are accessors
+/// for nodes, and \a ObjectStore::getReference().
+///
+/// \a ObjectStore::load() will load the referenced object, and returns \a
+/// ObjectHandle, a variant that knows what kind of entity it is. \a
+/// ObjectStore::getReferenceKind() can expect the type of reference without
+/// asking for unloaded objects to be loaded.
+///
+/// This is a wrapper around a \c uint64_t (and a \a ObjectStore instance when
+/// assertions are on). If necessary, it can be deconstructed and reconstructed
+/// using \a Reference::getInternalRef() and \a
+/// Reference::getFromInternalRef(), but clients aren't expected to need to do
+/// this. These both require the right \a ObjectStore instance.
+class ObjectRef : public ReferenceBase {
+  struct DenseMapTag {};
+
+public:
+  friend bool operator==(const ObjectRef &LHS, const ObjectRef &RHS) {
+    return LHS.hasSameInternalRef(RHS);
+  }
+  friend bool operator!=(const ObjectRef &LHS, const ObjectRef &RHS) {
+    return !(LHS == RHS);
+  }
+
+  /// Allow a reference to be recreated after it's deconstructed.
+  static ObjectRef getFromInternalRef(const ObjectStore &CAS,
+                                      uint64_t InternalRef) {
+    return ObjectRef(CAS, InternalRef);
+  }
+
+  static ObjectRef getDenseMapEmptyKey() {
+    return ObjectRef(DenseMapEmptyTag{});
+  }
+  static ObjectRef getDenseMapTombstoneKey() {
+    return ObjectRef(DenseMapTombstoneTag{});
+  }
+
+  /// Print internal ref and/or CASID. Only suitable for debugging.
+  void print(raw_ostream &OS) const { return ReferenceBase::print(OS, *this); }
+
+  LLVM_DUMP_METHOD void dump() const;
+
+private:
+  friend class ObjectStore;
+  friend class ReferenceBase;
+  using ReferenceBase::ReferenceBase;
+  ObjectRef(const ObjectStore &CAS, uint64_t InternalRef)
+      : ReferenceBase(&CAS, InternalRef, /*IsHandle=*/false) {
+    assert(InternalRef != -1ULL && "Reserved for DenseMapInfo");
+    assert(InternalRef != -2ULL && "Reserved for DenseMapInfo");
+  }
+  explicit ObjectRef(DenseMapEmptyTag T) : ReferenceBase(T) {}
+  explicit ObjectRef(DenseMapTombstoneTag T) : ReferenceBase(T) {}
+  explicit ObjectRef(ReferenceBase) = delete;
+};
+
+/// Handle to a loaded object in a \a ObjectStore instance.
+///
+/// ObjectHandle encapulates a *loaded* object in the CAS. You need one
+/// of these to inspect the content of an object: to look at its stored
+/// data and references.
+class ObjectHandle : public ReferenceBase {
+public:
+  friend bool operator==(const ObjectHandle &LHS, const ObjectHandle &RHS) {
+    return LHS.hasSameInternalRef(RHS);
+  }
+  friend bool operator!=(const ObjectHandle &LHS, const ObjectHandle &RHS) {
+    return !(LHS == RHS);
+  }
+
+  /// Print internal ref and/or CASID. Only suitable for debugging.
+  void print(raw_ostream &OS) const { return ReferenceBase::print(OS, *this); }
+
+  LLVM_DUMP_METHOD void dump() const;
+
+private:
+  friend class ObjectStore;
+  friend class ReferenceBase;
+  using ReferenceBase::ReferenceBase;
+  explicit ObjectHandle(ReferenceBase) = delete;
+  ObjectHandle(const ObjectStore &CAS, uint64_t InternalRef)
+      : ReferenceBase(&CAS, InternalRef, /*IsHandle=*/true) {}
+};
+
+} // namespace cas
+
+template <> struct DenseMapInfo<cas::ObjectRef> {
+  static cas::ObjectRef getEmptyKey() {
+    return cas::ObjectRef::getDenseMapEmptyKey();
+  }
+
+  static cas::ObjectRef getTombstoneKey() {
+    return cas::ObjectRef::getDenseMapTombstoneKey();
+  }
+
+  static unsigned getHashValue(cas::ObjectRef Ref) {
+    return Ref.getDenseMapHash();
+  }
+
+  static bool isEqual(cas::ObjectRef LHS, cas::ObjectRef RHS) {
+    return LHS == RHS;
+  }
+};
+
+} // namespace llvm
+
+#endif // LLVM_CAS_CASREFERENCE_H

llvm/include/llvm/CAS/ObjectStore.h

+//===- llvm/CAS/ObjectStore.h -----------------------------------------*- C++
+//-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CAS_OBJECTSTORE_H
+#define LLVM_CAS_OBJECTSTORE_H
+
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CAS/CASID.h"
+#include "llvm/CAS/CASReference.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+#include <cstddef>
+
+namespace llvm {
+
+class MemoryBuffer;
+
+namespace cas {
+
+class ObjectStore;
+class ObjectProxy;
+
+/// Content-addressable storage for objects.
+///
+/// Conceptually, objects are stored in a "unique set".
+///
+/// - Objects are immutable ("value objects") that are defined by their
+///   content. They are implicitly deduplicated by content.
+/// - Each object has a unique identifier (UID) that's derived from its content,
+///   called a \a CASID.
+///     - This UID is a fixed-size (strong) hash of the transitive content of a
+///       CAS object.
+///     - It's comparable between any two CAS instances that have the same \a
+///       CASIDContext::getHashSchemaIdentifier().
+///     - The UID can be printed (e.g., \a CASID::toString()) and it can parsed
+///       by the same or a different CAS instance with \a
+///       ObjectStore::parseID().
+/// - An object can be looked up by content or by UID.
+///     - \a store() is "get-or-create"  methods, writing an object if it
+///       doesn't exist yet, and return a ref to it in any case.
+///     - \a loadObject(const CASID&) looks up an object by its UID.
+/// - Objects can reference other objects, forming an arbitrary DAG.
+///
+/// The \a ObjectStore interface has a few ways of referencing objects:
+///
+/// - \a ObjectRef encapsulates a reference to something in the CAS. It is an
+///   opaque type that references an object inside a specific CAS. It is
+///   implementation defined if the underlying object exists or not for an
+///   ObjectRef, and it can used to speed up CAS lookup as an implementation
+///   detail. However, you don't know anything about the underlying objects.
+///   "Loading" the object is a separate step that may not have happened
+///   yet, and which can fail (e.g. due to filesystem corruption) or introduce
+///   latency (if downloading from a remote store).
+/// - \a ObjectHandle encapulates a *loaded* object in the CAS. You need one of
+///   these to inspect the content of an object: to look at its stored
+///   data and references. This is internal to CAS implementation and not
+///   availble from CAS public APIs.
+/// - \a CASID: the UID for an object in the CAS, obtained through \a
+///   ObjectStore::getID() or \a ObjectStore::parseID(). This is a valid CAS
+///   identifier, but may reference an object that is unknown to this CAS
+///   instance.
+/// - \a ObjectProxy pairs an ObjectHandle (subclass) with a ObjectStore, and
+///   wraps access APIs to avoid having to pass extra parameters. It is the
+///   object used for accessing underlying data and refs by CAS users.
+///
+/// There are a few options for accessing content of objects, with different
+/// lifetime tradeoffs:
+///
+/// - \a getData() accesses data without exposing lifetime at all.
+/// - \a loadIndependentDataBuffer() returns a \a MemoryBuffer whose lifetime
+///   is independent of the CAS (it can live longer).
+/// - \a getDataString() return StringRef with lifetime is guaranteed to last as
+///   long as \a ObjectStore.
+/// - \a readRef() and \a forEachRef() iterate through the references in an
+///   object. There is no lifetime assumption.
+///
+/// Both ObjectRef and ObjectHandle are lightweight, wrapping a `uint64_t`.
+/// Doing anything with them requires a ObjectStore. As a convenience:
+///
+class ObjectStore {
+  friend class ObjectProxy;
+  friend class ReferenceBase;
+  void anchor();
+
+public:
+  /// @name CASID Operations
+  /// {
+
+  /// Get a \p CASID from a \p ID, which should have been generated by \a
+  /// CASID::print(). This succeeds as long as \a validateID() would pass. The
+  /// object may be unknown to this CAS instance.
+  virtual Expected<CASID> parseID(StringRef ID) = 0;
+
+  /// Get an ID for \p Ref.
+  virtual CASID getID(ObjectRef Ref) const = 0;
+
+  /// Get a reference to the object called \p ID.
+  ///
+  /// Returns \c None if not stored in this CAS.
+  virtual Optional<ObjectRef> getReference(const CASID &ID) const = 0;
+
+  /// Validate the underlying object referred by CASID.
+  virtual Error validate(const CASID &ID) = 0;
+
+  /// }
+  /// @name Store Objects
+  /// {
+  /// Store object into ObjectStore.
+  virtual Expected<ObjectRef> store(ArrayRef<ObjectRef> Refs,
+                                    ArrayRef<char> Data) = 0;
+
+  /// Store object from StringRef.
+  Expected<ObjectRef> storeFromString(ArrayRef<ObjectRef> Refs,
+                                      StringRef String) {
+    return store(Refs, arrayRefFromStringRef<char>(String));
+  }
+
+  /// Helper functions to store object and returns a ObjectProxy.
+  Expected<ObjectProxy> createProxy(ArrayRef<ObjectRef> Refs, StringRef Data);
+
+  /// Default implementation reads \p FD and calls \a storeNode(). Does not
+  /// take ownership of \p FD; the caller is responsible for closing it.
+  ///
+  /// If \p Status is sent in it is to be treated as a hint. Implementations
+  /// must protect against the file size potentially growing after the status
+  /// was taken (i.e., they cannot assume that an mmap will be null-terminated
+  /// where \p Status implies).
+  ///
+  /// Returns the \a CASID and the size of the file.
+  Expected<ObjectRef>
+  storeFromOpenFile(sys::fs::file_t FD,
+                    Optional<sys::fs::file_status> Status = None) {
+    return storeFromOpenFileImpl(FD, Status);
+  }
+
+  /// }
+  /// @name Get Objects
+  /// {
+  /// Create ObjectProxy from CASID. If the object doesn't exit, get an error.
+  Expected<ObjectProxy> getProxy(const CASID &ID);
+  /// Create ObjectProxy from ObjectRef. If the object can't be loaded, get an
+  /// error.
+  Expected<ObjectProxy> getProxy(ObjectRef Ref);
+
+  /// Create ObjectProxy from CASID. If the object doesn't exit, get None.
+  Expected<Optional<ObjectProxy>> getProxyOrNone(const CASID &ID);
+
+  /// }
+protected:
+  /// @name Implementation Details for underlying CAS.
+  /// {
+  /// Get a Ref from Handle.
+  virtual ObjectRef getReference(ObjectHandle Handle) const = 0;
+
+  /// Load the object referenced by \p Ref.
+  ///
+  /// Errors if the object cannot be loaded.
+  virtual Expected<ObjectHandle> load(ObjectRef Ref) = 0;
+
+  /// Get an ID for \p Handle.
+  virtual CASID getID(ObjectHandle Handle) const = 0;
+
+  /// Get the size of some data.
+  virtual uint64_t getDataSize(ObjectHandle Node) const = 0;
+
+  /// Methods for handling objects.
+  virtual Error forEachRef(ObjectHandle Node,
+                           function_ref<Error(ObjectRef)> Callback) const = 0;
+  virtual ObjectRef readRef(ObjectHandle Node, size_t I) const = 0;
+  virtual size_t getNumRefs(ObjectHandle Node) const = 0;
+  virtual ArrayRef<char> getData(ObjectHandle Node,
+                                 bool RequiresNullTerminator = false) const = 0;
+
+  /// Get ObjectRef from open file.
+  virtual Expected<ObjectRef>
+  storeFromOpenFileImpl(sys::fs::file_t FD,
+                        Optional<sys::fs::file_status> Status) = 0;
+  /// }
+  /// @name Helper functions for implementing CAS.
+  /// {
+
+  /// Get a lifetime-extended StringRef pointing at \p Data.
+  ///
+  /// Depending on the CAS implementation, this may involve in-memory storage
+  /// overhead.
+  StringRef getDataString(ObjectHandle Node) {
+    return toStringRef(getData(Node));
+  }
+
+  /// Get a lifetime-extended MemoryBuffer pointing at \p Data.
+  ///
+  /// Depending on the CAS implementation, this may involve in-memory storage
+  /// overhead.
+  std::unique_ptr<MemoryBuffer>
+  getMemoryBuffer(ObjectHandle Node, StringRef Name = "",
+                  bool RequiresNullTerminator = true);
+
+  /// Helper function to chain `load(ObjectRef)` into ObjectProxy.
+  Expected<ObjectProxy> getProxy(Expected<ObjectHandle> Ref);
+
+  /// Read the data from \p Data into \p OS.
+  uint64_t readData(ObjectHandle Node, raw_ostream &OS, uint64_t Offset = 0,
+                    uint64_t MaxBytes = -1ULL) const {
+    ArrayRef<char> Data = getData(Node);
+    assert(Offset < Data.size() && "Expected valid offset");
+    Data = Data.drop_front(Offset).take_front(MaxBytes);
+    OS << toStringRef(Data);
+    return Data.size();
+  }
+
+  /// Allow ObjectStore implementations to create internal handles.
+#define MAKE_CAS_HANDLE_CONSTRUCTOR(HandleKind)                                \
+  HandleKind make##HandleKind(uint64_t InternalRef) const {                    \
+    return HandleKind(*this, InternalRef);                                     \
+  }
+  MAKE_CAS_HANDLE_CONSTRUCTOR(ObjectHandle)
+  MAKE_CAS_HANDLE_CONSTRUCTOR(ObjectRef)
+#undef MAKE_CAS_HANDLE_CONSTRUCTOR
+
+  /// Create an unknown object error.
+  static Error createUnknownObjectError(const CASID &ID);
+
+  /// }
+
+public:
+  /// Print the ObjectStore internals for debugging purpose.
+  virtual void print(raw_ostream &) const {}
+  void dump() const;
+
+  /// Get CASContext
+  const CASContext &getContext() const { return Context; }
+
+  virtual ~ObjectStore() = default;
+
+protected:
+  ObjectStore(const CASContext &Context) : Context(Context) {}
+
+private:
+  const CASContext &Context;
+};
+
+/// Reference to an abstract hierarchical node, with data and references.
+/// Reference is passed by value and is expected to be valid as long as the \a
+/// ObjectStore is.
+///
+/// TODO: Expose \a ObjectStore::readData() and only call \a
+/// ObjectStore::getDataString() when asked.
+class ObjectProxy {
+public:
+  const ObjectStore &getCAS() const { return *CAS; }
+  ObjectStore &getCAS() { return *CAS; }
+  CASID getID() const { return CAS->getID(H); }
+  ObjectRef getRef() const { return CAS->getReference(H); }
+  size_t getNumReferences() const { return CAS->getNumRefs(H); }
+  ObjectRef getReference(size_t I) const { return CAS->readRef(H, I); }
+
+  operator CASID() const { return getID(); }
+  CASID getReferenceID(size_t I) const {
+    Optional<CASID> ID = getCAS().getID(getReference(I));
+    assert(ID && "Expected reference to be first-class object");
+    return *ID;
+  }
+
+  /// Visit each reference in order, returning an error from \p Callback to
+  /// stop early.
+  Error forEachReference(function_ref<Error(ObjectRef)> Callback) const {
+    return CAS->forEachRef(H, Callback);
+  }
+  Error forEachReferenceID(function_ref<Error(CASID)> Callback) const {
+    return CAS->forEachRef(H, [&](ObjectRef Ref) {
+      Optional<CASID> ID = getCAS().getID(Ref);
+      assert(ID && "Expected reference to be first-class object");
+      return Callback(*ID);
+    });
+  }
+
+  std::unique_ptr<MemoryBuffer>
+  getMemoryBuffer(StringRef Name = "",
+                  bool RequiresNullTerminator = true) const;
+
+  /// Get the content of the node. Valid as long as the CAS is valid.
+  StringRef getData() const { return CAS->getDataString(H); }
+
+  friend bool operator==(const ObjectProxy &Proxy, ObjectRef Ref) {
+    return Proxy.getRef() == Ref;
+  }
+  friend bool operator==(ObjectRef Ref, const ObjectProxy &Proxy) {
+    return Proxy.getRef() == Ref;
+  }
+  friend bool operator!=(const ObjectProxy &Proxy, ObjectRef Ref) {
+    return !(Proxy.getRef() == Ref);
+  }
+  friend bool operator!=(ObjectRef Ref, const ObjectProxy &Proxy) {
+    return !(Proxy.getRef() == Ref);
+  }
+
+public:
+  ObjectProxy() = delete;
+
+  static ObjectProxy load(ObjectStore &CAS, ObjectHandle Node) {
+    return ObjectProxy(CAS, Node);
+  }
+
+private:
+  ObjectProxy(ObjectStore &CAS, ObjectHandle H) : CAS(&CAS), H(H) {}
+
+  ObjectStore *CAS;
+  ObjectHandle H;
+};
+
+Expected<std::unique_ptr<ObjectStore>>
+createPluginCAS(StringRef PluginPath, ArrayRef<std::string> PluginArgs = None);
+std::unique_ptr<ObjectStore> createInMemoryCAS();
+
+} // namespace cas
+} // namespace llvm
+
+#endif // LLVM_CAS_OBJECTSTORE_H

llvm/lib/CAS/BuiltinCAS.h

+//===- BuiltinCAS.h ---------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_CAS_BUILTINCAS_H
+#define LLVM_LIB_CAS_BUILTINCAS_H
+
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CAS/ObjectStore.h"
+#include "llvm/Support/BLAKE3.h"
+#include "llvm/Support/Error.h"
+#include <cstddef>
+
+namespace llvm::cas::builtin {
+
+/// Current hash type for the internal CAS.
+///
+/// FIXME: This should be configurable via an enum to allow configuring the hash
+/// function. The enum should be sent into \a createInMemoryCAS() and \a
+/// createOnDiskCAS().
+///
+/// This is important (at least) for future-proofing, when we want to make new
+/// CAS instances use BLAKE7, but still know how to read/write BLAKE3.
+///
+/// Even just for BLAKE3, it would be useful to have these values:
+///
+///     BLAKE3     => 32B hash from BLAKE3
+///     BLAKE3_16B => 16B hash from BLAKE3 (truncated)
+///
+/// ... where BLAKE3_16 uses \a TruncatedBLAKE3<16>.
+///
+/// Motivation for a truncated hash is that it's cheaper to store. It's not
+/// clear if we always (or ever) need the full 32B, and for an ephemeral
+/// in-memory CAS, we almost certainly don't need it.
+///
+/// Note that the cost is linear in the number of objects for the builtin CAS
+/// and embedded action cache, since we're using internal offsets and/or
+/// pointers as an optimization.
+///
+/// However, it's possible we'll want to hook up a local builtin CAS to, e.g.,
+/// a distributed generic hash map to use as an ActionCache. In that scenario,
+/// the transitive closure of the structured objects that are the results of
+/// the cached actions would need to be serialized into the map, something
+/// like:
+///
+///     "action:<schema>:<key>" -> "0123"
+///     "object:<schema>:0123"  -> "3,4567,89AB,CDEF,9,some data"
+///     "object:<schema>:4567"  -> ...
+///     "object:<schema>:89AB"  -> ...
+///     "object:<schema>:CDEF"  -> ...
+///
+/// These references would be full cost.
+using HasherT = BLAKE3;
+using HashType = decltype(HasherT::hash(std::declval<ArrayRef<uint8_t> &>()));
+
+class BuiltinCASContext : public CASContext {
+  void printIDImpl(raw_ostream &OS, const CASID &ID) const final;
+  void anchor() override;
+
+public:
+  /// Get the name of the hash for any table identifiers.
+  ///
+  /// FIXME: This should be configurable via an enum, with at the following
+  /// values:
+  ///
+  ///     "BLAKE3"    => 32B hash from BLAKE3
+  ///     "BLAKE3.16" => 16B hash from BLAKE3 (truncated)
+  ///
+  /// Enum can be sent into \a createInMemoryCAS() and \a createOnDiskCAS().
+  static StringRef getHashName() { return "BLAKE3"; }
+  StringRef getHashSchemaIdentifier() const final {
+    static const std::string ID =
+        ("llvm.cas.builtin.v2[" + getHashName() + "]").str();
+    return ID;
+  }
+
+  static const BuiltinCASContext &getDefaultContext();
+
+  BuiltinCASContext() = default;
+};
+
+class BuiltinCAS : public ObjectStore {
+public:
+  BuiltinCAS() : ObjectStore(BuiltinCASContext::getDefaultContext()) {}
+
+  Expected<CASID> parseID(StringRef Reference) final;
+
+  virtual Expected<CASID> parseIDImpl(ArrayRef<uint8_t> Hash) = 0;
+
+  Expected<ObjectRef> store(ArrayRef<ObjectRef> Refs,
+                            ArrayRef<char> Data) final;
+  virtual Expected<ObjectRef> storeImpl(ArrayRef<uint8_t> ComputedHash,
+                                        ArrayRef<ObjectRef> Refs,
+                                        ArrayRef<char> Data) = 0;
+
+  Expected<ObjectRef>
+  storeFromOpenFileImpl(sys::fs::file_t FD,
+                        Optional<sys::fs::file_status> Status) override;
+  virtual Expected<ObjectRef>
+  storeFromNullTerminatedRegion(ArrayRef<uint8_t> ComputedHash,
+                                sys::fs::mapped_file_region Map) {
+    return storeImpl(ComputedHash, None, makeArrayRef(Map.data(), Map.size()));
+  }
+
+  /// Both builtin CAS implementations provide lifetime for free, so this can
+  /// be const, and readData() and getDataSize() can be implemented on top of
+  /// it.
+  virtual ArrayRef<char> getDataConst(ObjectHandle Node) const = 0;
+
+  ArrayRef<char> getData(ObjectHandle Node,
+                         bool RequiresNullTerminator) const final {
+    // BuiltinCAS Objects are always null terminated.
+    return getDataConst(Node);
+  }
+  uint64_t getDataSize(ObjectHandle Node) const final {
+    return getDataConst(Node).size();
+  }
+
+  Error createUnknownObjectError(const CASID &ID) const {
+    return createStringError(std::make_error_code(std::errc::invalid_argument),
+                             "unknown object '" + ID.toString() + "'");
+  }
+
+  Error createCorruptObjectError(const CASID &ID) const {
+    return createStringError(std::make_error_code(std::errc::invalid_argument),
+                             "corrupt object '" + ID.toString() + "'");
+  }
+
+  Error createCorruptStorageError() const {
+    return createStringError(std::make_error_code(std::errc::invalid_argument),
+                             "corrupt storage");
+  }
+
+  Error validate(const CASID &ID) final;
+};
+
+// FIXME: Proxy not portable. Maybe also error-prone?
+constexpr StringLiteral DefaultDirProxy = "/^llvm::cas::builtin::default";
+constexpr StringLiteral DefaultDir = "llvm.cas.builtin.default";
+
+} // namespace llvm::cas::builtin
+
+#endif // LLVM_LIB_CAS_BUILTINCAS_H

llvm/lib/CAS/BuiltinCAS.cpp

+//===- BuiltinCAS.cpp -------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "BuiltinCAS.h"
+#include "BuiltinObjectHasher.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/Alignment.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Process.h"
+
+using namespace llvm;
+using namespace llvm::cas;
+using namespace llvm::cas::builtin;
+
+static StringRef getCASIDPrefix() { return "llvmcas://"; }
+void BuiltinCASContext::anchor() {}
+
+Expected<CASID> BuiltinCAS::parseID(StringRef Reference) {
+  if (!Reference.consume_front(getCASIDPrefix()))
+    return createStringError(std::make_error_code(std::errc::invalid_argument),
+                             "invalid cas-id '" + Reference + "'");
+
+  // FIXME: Allow shortened references?
+  if (Reference.size() != 2 * sizeof(HashType))
+    return createStringError(std::make_error_code(std::errc::invalid_argument),
+                             "wrong size for cas-id hash '" + Reference + "'");
+
+  std::string Binary;
+  if (!tryGetFromHex(Reference, Binary))
+    return createStringError(std::make_error_code(std::errc::invalid_argument),
+                             "invalid hash in cas-id '" + Reference + "'");
+
+  return parseIDImpl(arrayRefFromStringRef(Binary));
+}
+
+void BuiltinCASContext::printIDImpl(raw_ostream &OS, const CASID &ID) const {
+  SmallString<64> Hash;
+  toHex(ID.getHash(), /*LowerCase=*/true, Hash);
+  OS << getCASIDPrefix() << Hash;
+}
+
+const BuiltinCASContext &BuiltinCASContext::getDefaultContext() {
+  static BuiltinCASContext DefaultContext;
+  return DefaultContext;
+}
+
+static size_t getPageSize() {
+  static int PageSize = sys::Process::getPageSizeEstimate();
+  return PageSize;
+}
+
+Expected<ObjectRef>
+BuiltinCAS::storeFromOpenFileImpl(sys::fs::file_t FD,
+                                  Optional<sys::fs::file_status> Status) {
+  int PageSize = getPageSize();
+
+  if (!Status) {
+    Status.emplace();
+    if (std::error_code EC = sys::fs::status(FD, *Status))
+      return errorCodeToError(EC);
+  }
+
+  constexpr size_t MinMappedSize = 4 * 4096;
+  auto readWithStream = [&]() -> Expected<ObjectRef> {
+    // FIXME: MSVC: SmallString<MinMappedSize * 2>
+    SmallString<4 * 4096 * 2> Data;
+    if (Error E = sys::fs::readNativeFileToEOF(FD, Data, MinMappedSize))
+      return std::move(E);
+    return store(None, makeArrayRef(Data.data(), Data.size()));
+  };
+
+  // Check whether we can trust the size from stat.
+  if (Status->type() != sys::fs::file_type::regular_file &&
+      Status->type() != sys::fs::file_type::block_file)
+    return readWithStream();
+
+  if (Status->getSize() < MinMappedSize)
+    return readWithStream();
+
+  std::error_code EC;
+  sys::fs::mapped_file_region Map(FD, sys::fs::mapped_file_region::readonly,
+                                  Status->getSize(),
+                                  /*offset=*/0, EC);
+  if (EC)
+    return errorCodeToError(EC);
+
+  // If the file is guaranteed to be null-terminated, use it directly. Note
+  // that the file size may have changed from ::stat if this file is volatile,
+  // so we need to check for an actual null character at the end.
+  ArrayRef<char> Data(Map.data(), Map.size());
+  HashType ComputedHash =
+      BuiltinObjectHasher<HasherT>::hashObject(*this, None, Data);
+  if (!isAligned(Align(PageSize), Data.size()) && Data.end()[0] == 0)
+    return storeFromNullTerminatedRegion(ComputedHash, std::move(Map));
+  return storeImpl(ComputedHash, None, Data);
+}
+
+Expected<ObjectRef> BuiltinCAS::store(ArrayRef<ObjectRef> Refs,
+                                      ArrayRef<char> Data) {
+  return storeImpl(BuiltinObjectHasher<HasherT>::hashObject(*this, Refs, Data),
+                   Refs, Data);
+}
+
+Error BuiltinCAS::validate(const CASID &ID) {
+  auto Ref = getReference(ID);
+  if (!Ref)
+    return createUnknownObjectError(ID);
+
+  auto Handle = load(*Ref);
+  if (!Handle)
+    return Handle.takeError();
+
+  auto Proxy = ObjectProxy::load(*this, *Handle);
+  SmallVector<ObjectRef> Refs;
+  if (auto E = Proxy.forEachReference([&](ObjectRef Ref) -> Error {
+        Refs.push_back(Ref);
+        return Error::success();
+      }))
+    return E;
+
+  ArrayRef<char> Data(Proxy.getData().data(), Proxy.getData().size());
+  auto Hash = BuiltinObjectHasher<HasherT>::hashObject(*this, Refs, Data);
+  if (!ID.getHash().equals(Hash))
+    return createCorruptObjectError(ID);
+
+  return Error::success();
+}

llvm/lib/CAS/BuiltinObjectHasher.h

+//===- BuiltinObjectHasher.h ------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CAS_BUILTINOBJECTHASHER_H
+#define LLVM_CAS_BUILTINOBJECTHASHER_H
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CAS/ObjectStore.h"
+#include "llvm/Support/Endian.h"
+
+namespace llvm {
+namespace cas {
+
+template <class HasherT> class BuiltinObjectHasher {
+public:
+  using HashT = decltype(HasherT::hash(std::declval<ArrayRef<uint8_t> &>()));
+
+  static HashT hashObject(const ObjectStore &CAS, ArrayRef<ObjectRef> Refs,
+                          ArrayRef<char> Data) {
+    BuiltinObjectHasher H;
+    H.updateSize(Refs.size());
+    for (const ObjectRef &Ref : Refs)
+      H.updateRef(CAS, Ref);
+    H.updateArray(Data);
+    return H.finish();
+  }
+
+private:
+  HashT finish() { return Hasher.final(); }
+
+  void updateRef(const ObjectStore &CAS, ObjectRef Ref) {
+    updateID(CAS.getID(Ref));
+  }
+
+  void updateID(const CASID &ID) {
+    // NOTE: Does not hash the size of the hash. That's a CAS implementation
+    // detail that shouldn't leak into the UUID for an object.
+    ArrayRef<uint8_t> Hash = ID.getHash();
+    assert(Hash.size() == sizeof(HashT) &&
+           "Expected object ref to match the hash size");
+    Hasher.update(Hash);
+  }
+
+  void updateArray(ArrayRef<uint8_t> Bytes) {
+    updateSize(Bytes.size());
+    Hasher.update(Bytes);
+  }
+
+  void updateArray(ArrayRef<char> Bytes) {
+    updateArray(makeArrayRef(reinterpret_cast<const uint8_t *>(Bytes.data()),
+                             Bytes.size()));
+  }
+
+  void updateSize(uint64_t Size) {
+    Size = support::endian::byte_swap(Size, support::endianness::little);
+    Hasher.update(
+        makeArrayRef(reinterpret_cast<const uint8_t *>(&Size), sizeof(Size)));
+  }
+
+  BuiltinObjectHasher() = default;
+  ~BuiltinObjectHasher() = default;
+  HasherT Hasher;
+};
+
+} // namespace cas
+} // namespace llvm
+
+#endif // LLVM_CAS_BUILTINOBJECTHASHER_H

llvm/lib/CAS/CMakeLists.txt

+add_llvm_component_library(LLVMCAS
+  BuiltinCAS.cpp
+  InMemoryCAS.cpp
+  ObjectStore.cpp
+
+  ADDITIONAL_HEADER_DIRS
+  ${LLVM_MAIN_INCLUDE_DIR}/llvm/CAS
+)

llvm/lib/CAS/InMemoryCAS.cpp

+//===- InMemoryCAS.cpp ------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "BuiltinCAS.h"
+#include "BuiltinObjectHasher.h"
+#include "llvm/ADT/HashMappedTrie.h"
+#include "llvm/ADT/LazyAtomicPointer.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/ThreadSafeAllocator.h"
+
+using namespace llvm;
+using namespace llvm::cas;
+using namespace llvm::cas::builtin;
+
+namespace {
+
+class InMemoryObject;
+
+/// Index of referenced IDs (map: Hash -> InMemoryObject*). Uses
+/// LazyAtomicPointer to coordinate creation of objects.
+using InMemoryIndexT =
+    ThreadSafeHashMappedTrie<LazyAtomicPointer<const InMemoryObject>,
+                             sizeof(HashType)>;
+
+/// Values in \a InMemoryIndexT. \a InMemoryObject's point at this to access
+/// their hash.
+using InMemoryIndexValueT = InMemoryIndexT::value_type;
+
+class InMemoryObject {
+public:
+  enum class Kind {
+    /// Node with refs and data.
+    RefNode,
+
+    /// Node with refs and data co-allocated.
+    InlineNode,
+
+    Max = InlineNode,
+  };
+
+  Kind getKind() const { return IndexAndKind.getInt(); }
+  const InMemoryIndexValueT &getIndex() const {
+    assert(IndexAndKind.getPointer());
+    return *IndexAndKind.getPointer();
+  }
+
+  ArrayRef<uint8_t> getHash() const { return getIndex().Hash; }
+
+  InMemoryObject() = delete;
+  InMemoryObject(InMemoryObject &&) = delete;
+  InMemoryObject(const InMemoryObject &) = delete;
+
+protected:
+  InMemoryObject(Kind K, const InMemoryIndexValueT &I) : IndexAndKind(&I, K) {}
+
+private:
+  enum Counts : int {
+    NumKindBits = 2,
+  };
+  PointerIntPair<const InMemoryIndexValueT *, NumKindBits, Kind> IndexAndKind;
+  static_assert((1U << NumKindBits) <= alignof(InMemoryIndexValueT),
+                "Kind will clobber pointer");
+  static_assert(((int)Kind::Max >> NumKindBits) == 0, "Kind will be truncated");
+
+public:
+  inline ArrayRef<char> getData() const;
+
+  inline ArrayRef<const InMemoryObject *> getRefs() const;
+};
+
+class InMemoryRefObject : public InMemoryObject {
+public:
+  static constexpr Kind KindValue = Kind::RefNode;
+  static bool classof(const InMemoryObject *O) {
+    return O->getKind() == KindValue;
+  }
+
+  ArrayRef<const InMemoryObject *> getRefsImpl() const { return Refs; }
+  ArrayRef<const InMemoryObject *> getRefs() const { return Refs; }
+  ArrayRef<char> getDataImpl() const { return Data; }
+  ArrayRef<char> getData() const { return Data; }
+
+  static InMemoryRefObject &create(function_ref<void *(size_t Size)> Allocate,
+                                   const InMemoryIndexValueT &I,
+                                   ArrayRef<const InMemoryObject *> Refs,
+                                   ArrayRef<char> Data) {
+    void *Mem = Allocate(sizeof(InMemoryRefObject));
+    return *new (Mem) InMemoryRefObject(I, Refs, Data);
+  }
+
+private:
+  InMemoryRefObject(const InMemoryIndexValueT &I,
+                    ArrayRef<const InMemoryObject *> Refs, ArrayRef<char> Data)
+      : InMemoryObject(KindValue, I), Refs(Refs), Data(Data) {
+    assert(isAddrAligned(Align(8), this) && "Expected 8-byte alignment");
+    assert(isAddrAligned(Align(8), Data.data()) && "Expected 8-byte alignment");
+    assert(*Data.end() == 0 && "Expected null-termination");
+  }
+
+  ArrayRef<const InMemoryObject *> Refs;
+  ArrayRef<char> Data;
+};
+
+class InMemoryInlineObject : public InMemoryObject {
+public:
+  static constexpr Kind KindValue = Kind::InlineNode;
+  static bool classof(const InMemoryObject *O) {
+    return O->getKind() == KindValue;
+  }
+
+  ArrayRef<const InMemoryObject *> getRefs() const { return getRefsImpl(); }
+  ArrayRef<const InMemoryObject *> getRefsImpl() const {
+    return makeArrayRef(
+        reinterpret_cast<const InMemoryObject *const *>(this + 1), NumRefs);
+  }
+
+  ArrayRef<char> getData() const { return getDataImpl(); }
+  ArrayRef<char> getDataImpl() const {
+    ArrayRef<const InMemoryObject *> Refs = getRefs();
+    return makeArrayRef(
+        reinterpret_cast<const char *>(Refs.data() + Refs.size()), DataSize);
+  }
+
+  static InMemoryInlineObject &
+  create(function_ref<void *(size_t Size)> Allocate,
+         const InMemoryIndexValueT &I, ArrayRef<const InMemoryObject *> Refs,
+         ArrayRef<char> Data) {
+    void *Mem = Allocate(sizeof(InMemoryInlineObject) +
+                         sizeof(uintptr_t) * Refs.size() + Data.size() + 1);
+    return *new (Mem) InMemoryInlineObject(I, Refs, Data);
+  }
+
+private:
+  InMemoryInlineObject(const InMemoryIndexValueT &I,
+                       ArrayRef<const InMemoryObject *> Refs,
+                       ArrayRef<char> Data)
+      : InMemoryObject(KindValue, I), NumRefs(Refs.size()),
+        DataSize(Data.size()) {
+    auto *BeginRefs = reinterpret_cast<const InMemoryObject **>(this + 1);
+    llvm::copy(Refs, BeginRefs);
+    auto *BeginData = reinterpret_cast<char *>(BeginRefs + NumRefs);
+    llvm::copy(Data, BeginData);
+    BeginData[Data.size()] = 0;
+  }
+  uint32_t NumRefs;
+  uint32_t DataSize;
+};
+
+/// In-memory CAS database.
+class InMemoryCAS : public BuiltinCAS {
+public:
+  Expected<CASID> parseIDImpl(ArrayRef<uint8_t> Hash) final {
+    return getID(indexHash(Hash));
+  }
+
+  Expected<ObjectRef> storeImpl(ArrayRef<uint8_t> ComputedHash,
+                                ArrayRef<ObjectRef> Refs,
+                                ArrayRef<char> Data) final;
+
+  Expected<ObjectRef>
+  storeFromNullTerminatedRegion(ArrayRef<uint8_t> ComputedHash,
+                                sys::fs::mapped_file_region Map) override;
+
+  CASID getID(const InMemoryIndexValueT &I) const {
+    StringRef Hash = toStringRef(I.Hash);
+    return CASID::create(&getContext(), Hash);
+  }
+  CASID getID(const InMemoryObject &O) const { return getID(O.getIndex()); }
+
+  ObjectHandle getObjectHandle(const InMemoryObject &Node) const {
+    assert(!(reinterpret_cast<uintptr_t>(&Node) & 0x1ULL));
+    return makeObjectHandle(reinterpret_cast<uintptr_t>(&Node));
+  }
+
+  Expected<ObjectHandle> load(ObjectRef Ref) override {
+    return getObjectHandle(asInMemoryObject(Ref));
+  }
+
+  InMemoryIndexValueT &indexHash(ArrayRef<uint8_t> Hash) {
+    return *Index.insertLazy(
+        Hash, [](auto ValueConstructor) { ValueConstructor.emplace(nullptr); });
+  }
+
+  /// TODO: Consider callers to actually do an insert and to return a handle to
+  /// the slot in the trie.
+  const InMemoryObject *getInMemoryObject(CASID ID) const {
+    assert(ID.getContext().getHashSchemaIdentifier() ==
+               getContext().getHashSchemaIdentifier() &&
+           "Expected ID from same hash schema");
+    if (InMemoryIndexT::const_pointer P = Index.find(ID.getHash()))
+      return P->Data;
+    return nullptr;
+  }
+
+  const InMemoryObject &getInMemoryObject(ObjectHandle OH) const {
+    return *reinterpret_cast<const InMemoryObject *>(
+        (uintptr_t)OH.getInternalRef(*this));
+  }
+
+  const InMemoryObject &asInMemoryObject(ReferenceBase Ref) const {
+    uintptr_t P = Ref.getInternalRef(*this);
+    return *reinterpret_cast<const InMemoryObject *>(P);
+  }
+  ObjectRef toReference(const InMemoryObject &O) const {
+    return makeObjectRef(reinterpret_cast<uintptr_t>(&O));
+  }
+
+  CASID getID(ObjectRef Ref) const final { return getIDImpl(Ref); }
+  CASID getID(ObjectHandle Ref) const final { return getIDImpl(Ref); }
+  CASID getIDImpl(ReferenceBase Ref) const {
+    return getID(asInMemoryObject(Ref));
+  }
+
+  Optional<ObjectRef> getReference(const CASID &ID) const final {
+    if (const InMemoryObject *Object = getInMemoryObject(ID))
+      return toReference(*Object);
+    return None;
+  }
+  ObjectRef getReference(ObjectHandle Handle) const final {
+    return toReference(asInMemoryObject(Handle));
+  }
+
+  ArrayRef<char> getDataConst(ObjectHandle Node) const final {
+    return cast<InMemoryObject>(asInMemoryObject(Node)).getData();
+  }
+
+  void print(raw_ostream &OS) const final;
+
+  InMemoryCAS() = default;
+
+private:
+  size_t getNumRefs(ObjectHandle Node) const final {
+    return getInMemoryObject(Node).getRefs().size();
+  }
+  ObjectRef readRef(ObjectHandle Node, size_t I) const final {
+    return toReference(*getInMemoryObject(Node).getRefs()[I]);
+  }
+  Error forEachRef(ObjectHandle Node,
+                   function_ref<Error(ObjectRef)> Callback) const final;
+
+  /// Index of referenced IDs (map: Hash -> InMemoryObject*). Mapped to nullptr
+  /// as a convenient way to store hashes.
+  ///
+  /// - Insert nullptr on lookups.
+  /// - InMemoryObject points back to here.
+  InMemoryIndexT Index;
+
+  ThreadSafeAllocator<BumpPtrAllocator> Objects;
+  ThreadSafeAllocator<SpecificBumpPtrAllocator<sys::fs::mapped_file_region>>
+      MemoryMaps;
+};
+
+} // end anonymous namespace
+
+ArrayRef<char> InMemoryObject::getData() const {
+  if (auto *Derived = dyn_cast<InMemoryRefObject>(this))
+    return Derived->getDataImpl();
+  return cast<InMemoryInlineObject>(this)->getDataImpl();
+}
+
+ArrayRef<const InMemoryObject *> InMemoryObject::getRefs() const {
+  if (auto *Derived = dyn_cast<InMemoryRefObject>(this))
+    return Derived->getRefsImpl();
+  return cast<InMemoryInlineObject>(this)->getRefsImpl();
+}
+
+void InMemoryCAS::print(raw_ostream &OS) const {
+  OS << "index: ";
+  Index.print(OS);
+}
+
+Expected<ObjectRef>
+InMemoryCAS::storeFromNullTerminatedRegion(ArrayRef<uint8_t> ComputedHash,
+                                           sys::fs::mapped_file_region Map) {
+  // Look up the hash in the index, initializing to nullptr if it's new.
+  ArrayRef<char> Data(Map.data(), Map.size());
+  auto &I = indexHash(ComputedHash);
+
+  // Load or generate.
+  auto Allocator = [&](size_t Size) -> void * {
+    return Objects.Allocate(Size, alignof(InMemoryObject));
+  };
+  auto Generator = [&]() -> const InMemoryObject * {
+    return &InMemoryRefObject::create(Allocator, I, None, Data);
+  };
+  const InMemoryObject &Node =
+      cast<InMemoryObject>(I.Data.loadOrGenerate(Generator));
+
+  // Save Map if the winning node uses it.
+  if (auto *RefNode = dyn_cast<InMemoryRefObject>(&Node))
+    if (RefNode->getData().data() == Map.data())
+      new (MemoryMaps.Allocate()) sys::fs::mapped_file_region(std::move(Map));
+
+  return toReference(Node);
+}
+
+Expected<ObjectRef> InMemoryCAS::storeImpl(ArrayRef<uint8_t> ComputedHash,
+                                           ArrayRef<ObjectRef> Refs,
+                                           ArrayRef<char> Data) {
+  // Look up the hash in the index, initializing to nullptr if it's new.
+  auto &I = indexHash(ComputedHash);
+
+  // Create the node.
+  SmallVector<const InMemoryObject *> InternalRefs;
+  for (ObjectRef Ref : Refs)
+    InternalRefs.push_back(&asInMemoryObject(Ref));
+  auto Allocator = [&](size_t Size) -> void * {
+    return Objects.Allocate(Size, alignof(InMemoryObject));
+  };
+  auto Generator = [&]() -> const InMemoryObject * {
+    return &InMemoryInlineObject::create(Allocator, I, InternalRefs, Data);
+  };
+  return toReference(cast<InMemoryObject>(I.Data.loadOrGenerate(Generator)));
+}
+
+Error InMemoryCAS::forEachRef(ObjectHandle Handle,
+                              function_ref<Error(ObjectRef)> Callback) const {
+  auto &Node = getInMemoryObject(Handle);
+  for (const InMemoryObject *Ref : Node.getRefs())
+    if (Error E = Callback(toReference(*Ref)))
+      return E;
+  return Error::success();
+}
+
+std::unique_ptr<ObjectStore> cas::createInMemoryCAS() {
+  return std::make_unique<InMemoryCAS>();
+}

llvm/lib/CAS/ObjectStore.cpp

+//===- ObjectStore.cpp ------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CAS/ObjectStore.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/SmallVectorMemoryBuffer.h"
+
+using namespace llvm;
+using namespace llvm::cas;
+
+void CASContext::anchor() {}
+void ObjectStore::anchor() {}
+
+LLVM_DUMP_METHOD void CASID::dump() const { print(dbgs()); }
+LLVM_DUMP_METHOD void ObjectStore::dump() const { print(dbgs()); }
+LLVM_DUMP_METHOD void ObjectRef::dump() const { print(dbgs()); }
+LLVM_DUMP_METHOD void ObjectHandle::dump() const { print(dbgs()); }
+
+std::string CASID::toString() const {
+  std::string S;
+  raw_string_ostream(S) << *this;
+  return S;
+}
+
+ArrayRef<uint8_t> CASID::getHash() const {
+  return arrayRefFromStringRef<uint8_t>(Hash);
+}
+
+static void printReferenceBase(raw_ostream &OS, StringRef Kind,
+                               uint64_t InternalRef, Optional<CASID> ID) {
+  OS << Kind << "=" << InternalRef;
+  if (ID)
+    OS << "[" << *ID << "]";
+}
+
+void ReferenceBase::print(raw_ostream &OS, const ObjectHandle &This) const {
+  assert(this == &This);
+
+  Optional<CASID> ID;
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+  if (CAS)
+    ID = CAS->getID(This);
+#endif
+  printReferenceBase(OS, "object-handle", InternalRef, ID);
+}
+
+void ReferenceBase::print(raw_ostream &OS, const ObjectRef &This) const {
+  assert(this == &This);
+
+  Optional<CASID> ID;
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+  if (CAS)
+    ID = CAS->getID(This);
+#endif
+  printReferenceBase(OS, "object-ref", InternalRef, ID);
+}
+
+std::unique_ptr<MemoryBuffer>
+ObjectStore::getMemoryBuffer(ObjectHandle Node, StringRef Name,
+                             bool RequiresNullTerminator) {
+  return MemoryBuffer::getMemBuffer(
+      toStringRef(getData(Node, RequiresNullTerminator)), Name,
+      RequiresNullTerminator);
+}
+
+Expected<ObjectProxy> ObjectStore::getProxy(const CASID &ID) {
+  Optional<ObjectRef> Ref = getReference(ID);
+  if (!Ref)
+    return createUnknownObjectError(ID);
+
+  Optional<ObjectHandle> H;
+  if (Error E = load(*Ref).moveInto(H))
+    return std::move(E);
+
+  return ObjectProxy::load(*this, *H);
+}
+
+Expected<Optional<ObjectProxy>> ObjectStore::getProxyOrNone(const CASID &ID) {
+  Optional<ObjectRef> Ref = getReference(ID);
+  if (!Ref)
+    return None;
+
+  Optional<ObjectHandle> H;
+  if (Error E = load(*Ref).moveInto(H))
+    return std::move(E);
+
+  return ObjectProxy::load(*this, *H);
+}
+
+Expected<ObjectProxy> ObjectStore::getProxy(ObjectRef Ref) {
+  return getProxy(load(Ref));
+}
+
+Expected<ObjectProxy> ObjectStore::getProxy(Expected<ObjectHandle> H) {
+  if (!H)
+    return H.takeError();
+  return ObjectProxy::load(*this, *H);
+}
+
+Error ObjectStore::createUnknownObjectError(const CASID &ID) {
+  return createStringError(std::make_error_code(std::errc::invalid_argument),
+                           "unknown object '" + ID.toString() + "'");
+}
+
+Expected<ObjectProxy> ObjectStore::createProxy(ArrayRef<ObjectRef> Refs,
+                                               StringRef Data) {
+  Expected<ObjectRef> Ref = store(Refs, arrayRefFromStringRef<char>(Data));
+  if (!Ref)
+    return Ref.takeError();
+  return getProxy(*Ref);
+}
+
+std::unique_ptr<MemoryBuffer>
+ObjectProxy::getMemoryBuffer(StringRef Name,
+                             bool RequiresNullTerminator) const {
+  return CAS->getMemoryBuffer(H, Name, RequiresNullTerminator);
+}

llvm/lib/CMakeLists.txt

 include(LLVM-Build)
 
 # `Demangle', `Support' and `TableGen' libraries are added on the top-level
 # CMakeLists.txt
 
 add_subdirectory(IR)
 add_subdirectory(FuzzMutate)
 add_subdirectory(FileCheck)
 add_subdirectory(InterfaceStub)
 add_subdirectory(IRReader)
+add_subdirectory(CAS)
 add_subdirectory(CodeGen)
 add_subdirectory(BinaryFormat)
 add_subdirectory(Bitcode)
 add_subdirectory(Bitstream)
 add_subdirectory(DWARFLinker)
 add_subdirectory(Extensions)
 add_subdirectory(Frontend)
 add_subdirectory(Transforms)

llvm/unittests/CAS/CASTestConfig.h

+//===- CASTestConfig.h ----------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CAS/ObjectStore.h"
+#include "llvm/Config/llvm-config.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Testing/Support/Error.h"
+#include "llvm/Testing/Support/SupportHelpers.h"
+#include "gtest/gtest.h"
+
+#ifndef LLVM_UNITTESTS_CASTESTCONFIG_H
+#define LLVM_UNITTESTS_CASTESTCONFIG_H
+
+struct CASTestingEnv {
+  std::unique_ptr<llvm::cas::ObjectStore> CAS;
+};
+
+class CASTest
+    : public testing::TestWithParam<std::function<CASTestingEnv(int)>> {
+protected:
+  llvm::Optional<int> NextCASIndex;
+
+  std::unique_ptr<llvm::cas::ObjectStore> createObjectStore() {
+    auto TD = GetParam()(++(*NextCASIndex));
+    return std::move(TD.CAS);
+  }
+  void SetUp() { NextCASIndex = 0; }
+  void TearDown() { NextCASIndex = llvm::None; }
+};
+
+#endif

llvm/unittests/CAS/CASTestConfig.cpp

+//===- CASTestConfig.cpp --------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "CASTestConfig.h"
+#include "llvm/CAS/ObjectStore.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace llvm::cas;
+
+CASTestingEnv createInMemory(int I) {
+  std::unique_ptr<ObjectStore> CAS = createInMemoryCAS();
+  return CASTestingEnv{std::move(CAS)};
+}
+
+INSTANTIATE_TEST_SUITE_P(InMemoryCAS, CASTest,
+                         ::testing::Values(createInMemory));

llvm/unittests/CAS/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Support
+  CAS
+  TestingSupport
+  )
+
+add_llvm_unittest(CASTests
+  CASTestConfig.cpp
+  ObjectStoreTest.cpp
+  )
+
+target_link_libraries(CASTests PRIVATE LLVMTestingSupport)

llvm/unittests/CAS/ObjectStoreTest.cpp

+//===- ObjectStoreTest.cpp ------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CAS/ObjectStore.h"
+#include "llvm/Config/llvm-config.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Testing/Support/Error.h"
+#include "llvm/Testing/Support/SupportHelpers.h"
+#include "gtest/gtest.h"
+
+#include "CASTestConfig.h"
+
+using namespace llvm;
+using namespace llvm::cas;
+
+TEST_P(CASTest, PrintIDs) {
+  std::unique_ptr<ObjectStore> CAS = createObjectStore();
+
+  Optional<CASID> ID1, ID2;
+  ASSERT_THAT_ERROR(CAS->createProxy(None, "1").moveInto(ID1), Succeeded());
+  ASSERT_THAT_ERROR(CAS->createProxy(None, "2").moveInto(ID2), Succeeded());
+  EXPECT_NE(ID1, ID2);
+  std::string PrintedID1 = ID1->toString();
+  std::string PrintedID2 = ID2->toString();
+  EXPECT_NE(PrintedID1, PrintedID2);
+
+  Optional<CASID> ParsedID1, ParsedID2;
+  ASSERT_THAT_ERROR(CAS->parseID(PrintedID1).moveInto(ParsedID1), Succeeded());
+  ASSERT_THAT_ERROR(CAS->parseID(PrintedID2).moveInto(ParsedID2), Succeeded());
+  EXPECT_EQ(ID1, ParsedID1);
+  EXPECT_EQ(ID2, ParsedID2);
+}
+
+TEST_P(CASTest, Blobs) {
+  std::unique_ptr<ObjectStore> CAS1 = createObjectStore();
+  StringRef ContentStrings[] = {
+      "word",
+      "some longer text std::string's local memory",
+      R"(multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text)",
+  };
+
+  SmallVector<CASID> IDs;
+  for (StringRef Content : ContentStrings) {
+    // Use StringRef::str() to create a temporary std::string. This could cause
+    // problems if the CAS is storing references to the input string instead of
+    // copying it.
+    Optional<ObjectProxy> Blob;
+    ASSERT_THAT_ERROR(CAS1->createProxy(None, Content).moveInto(Blob),
+                      Succeeded());
+    IDs.push_back(Blob->getID());
+
+    // Check basic printing of IDs.
+    EXPECT_EQ(IDs.back().toString(), IDs.back().toString());
+    if (IDs.size() > 2)
+      EXPECT_NE(IDs.front().toString(), IDs.back().toString());
+  }
+
+  // Check that the blobs give the same IDs later.
+  for (int I = 0, E = IDs.size(); I != E; ++I) {
+    Optional<ObjectProxy> Blob;
+    ASSERT_THAT_ERROR(CAS1->createProxy(None, ContentStrings[I]).moveInto(Blob),
+                      Succeeded());
+    EXPECT_EQ(IDs[I], Blob->getID());
+  }
+
+  // Run validation on all CASIDs.
+  for (int I = 0, E = IDs.size(); I != E; ++I)
+    ASSERT_THAT_ERROR(CAS1->validate(IDs[I]), Succeeded());
+
+  // Check that the blobs can be retrieved multiple times.
+  for (int I = 0, E = IDs.size(); I != E; ++I) {
+    for (int J = 0, JE = 3; J != JE; ++J) {
+      Optional<ObjectProxy> Buffer;
+      ASSERT_THAT_ERROR(CAS1->getProxy(IDs[I]).moveInto(Buffer), Succeeded());
+      EXPECT_EQ(ContentStrings[I], Buffer->getData());
+    }
+  }
+
+  // Confirm these blobs don't exist in a fresh CAS instance.
+  std::unique_ptr<ObjectStore> CAS2 = createObjectStore();
+  for (int I = 0, E = IDs.size(); I != E; ++I) {
+    Optional<ObjectProxy> Proxy;
+    EXPECT_THAT_ERROR(CAS2->getProxyOrNone(IDs[I]).moveInto(Proxy),
+                      Succeeded());
+    ASSERT_FALSE(Proxy);
+  }
+
+  // Insert into the second CAS and confirm the IDs are stable. Getting them
+  // should work now.
+  for (int I = IDs.size(), E = 0; I != E; --I) {
+    auto &ID = IDs[I - 1];
+    auto &Content = ContentStrings[I - 1];
+    Optional<ObjectProxy> Blob;
+    ASSERT_THAT_ERROR(CAS2->createProxy(None, Content).moveInto(Blob),
+                      Succeeded());
+    EXPECT_EQ(ID, Blob->getID());
+
+    Optional<ObjectProxy> Buffer;
+    ASSERT_THAT_ERROR(CAS2->getProxy(ID).moveInto(Buffer), Succeeded());
+    EXPECT_EQ(Content, Buffer->getData());
+  }
+}
+
+TEST_P(CASTest, BlobsBig) {
+  // A little bit of validation that bigger blobs are okay. Climb up to 1MB.
+  std::unique_ptr<ObjectStore> CAS = createObjectStore();
+  SmallString<256> String1 = StringRef("a few words");
+  SmallString<256> String2 = StringRef("others");
+  while (String1.size() < 1024U * 1024U) {
+    Optional<CASID> ID1;
+    Optional<CASID> ID2;
+    ASSERT_THAT_ERROR(CAS->createProxy(None, String1).moveInto(ID1),
+                      Succeeded());
+    ASSERT_THAT_ERROR(CAS->createProxy(None, String1).moveInto(ID2),
+                      Succeeded());
+    ASSERT_THAT_ERROR(CAS->validate(*ID1), Succeeded());
+    ASSERT_THAT_ERROR(CAS->validate(*ID2), Succeeded());
+    ASSERT_EQ(ID1, ID2);
+
+    String1.append(String2);
+    ASSERT_THAT_ERROR(CAS->createProxy(None, String2).moveInto(ID1),
+                      Succeeded());
+    ASSERT_THAT_ERROR(CAS->createProxy(None, String2).moveInto(ID2),
+                      Succeeded());
+    ASSERT_THAT_ERROR(CAS->validate(*ID1), Succeeded());
+    ASSERT_THAT_ERROR(CAS->validate(*ID2), Succeeded());
+    ASSERT_EQ(ID1, ID2);
+    String2.append(String1);
+  }
+
+  // Specifically check near 1MB for objects large enough they're likely to be
+  // stored externally in an on-disk CAS and will be near a page boundary.
+  SmallString<0> Storage;
+  const size_t InterestingSize = 1024U * 1024ULL;
+  const size_t SizeE = InterestingSize + 2;
+  if (Storage.size() < SizeE)
+    Storage.resize(SizeE, '\01');
+  for (size_t Size = InterestingSize - 2; Size != SizeE; ++Size) {
+    StringRef Data(Storage.data(), Size);
+    Optional<ObjectProxy> Blob;
+    ASSERT_THAT_ERROR(CAS->createProxy(None, Data).moveInto(Blob), Succeeded());
+    ASSERT_EQ(Data, Blob->getData());
+    ASSERT_EQ(0, Blob->getData().end()[0]);
+  }
+}
+
+TEST_P(CASTest, LeafNodes) {
+  std::unique_ptr<ObjectStore> CAS1 = createObjectStore();
+  StringRef ContentStrings[] = {
+      "word",
+      "some longer text std::string's local memory",
+      R"(multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text
+multiline text multiline text multiline text multiline text multiline text)",
+  };
+
+  SmallVector<ObjectRef> Nodes;
+  SmallVector<CASID> IDs;
+  for (StringRef Content : ContentStrings) {
+    // Use StringRef::str() to create a temporary std::string. This could cause
+    // problems if the CAS is storing references to the input string instead of
+    // copying it.
+    Optional<ObjectRef> Node;
+    ASSERT_THAT_ERROR(
+        CAS1->store(None, arrayRefFromStringRef<char>(Content)).moveInto(Node),
+        Succeeded());
+    Nodes.push_back(*Node);
+
+    // Check basic printing of IDs.
+    IDs.push_back(CAS1->getID(*Node));
+    EXPECT_EQ(IDs.back().toString(), IDs.back().toString());
+    EXPECT_EQ(Nodes.front(), Nodes.front());
+    EXPECT_EQ(Nodes.back(), Nodes.back());
+    EXPECT_EQ(IDs.front(), IDs.front());
+    EXPECT_EQ(IDs.back(), IDs.back());
+    if (Nodes.size() <= 1)
+      continue;
+    EXPECT_NE(Nodes.front(), Nodes.back());
+    EXPECT_NE(IDs.front(), IDs.back());
+  }
+
+  // Check that the blobs give the same IDs later.
+  for (int I = 0, E = IDs.size(); I != E; ++I) {
+    Optional<ObjectRef> Node;
+    ASSERT_THAT_ERROR(
+        CAS1->store(None, arrayRefFromStringRef<char>(ContentStrings[I]))
+            .moveInto(Node),
+        Succeeded());
+    EXPECT_EQ(IDs[I], CAS1->getID(*Node));
+  }
+
+  // Check that the blobs can be retrieved multiple times.
+  for (int I = 0, E = IDs.size(); I != E; ++I) {
+    for (int J = 0, JE = 3; J != JE; ++J) {
+      Optional<ObjectProxy> Object;
+      ASSERT_THAT_ERROR(CAS1->getProxy(IDs[I]).moveInto(Object), Succeeded());
+      ASSERT_TRUE(Object);
+      EXPECT_EQ(ContentStrings[I], Object->getData());
+    }
+  }
+
+  // Confirm these blobs don't exist in a fresh CAS instance.
+  std::unique_ptr<ObjectStore> CAS2 = createObjectStore();
+  for (int I = 0, E = IDs.size(); I != E; ++I) {
+    Optional<ObjectProxy> Object;
+    EXPECT_THAT_ERROR(CAS2->getProxyOrNone(IDs[I]).moveInto(Object),
+                      Succeeded());
+    EXPECT_FALSE(Object);
+  }
+
+  // Insert into the second CAS and confirm the IDs are stable. Getting them
+  // should work now.
+  for (int I = IDs.size(), E = 0; I != E; --I) {
+    auto &ID = IDs[I - 1];
+    auto &Content = ContentStrings[I - 1];
+    Optional<ObjectRef> Node;
+    ASSERT_THAT_ERROR(
+        CAS2->store(None, arrayRefFromStringRef<char>(Content)).moveInto(Node),
+        Succeeded());
+    EXPECT_EQ(ID, CAS2->getID(*Node));
+
+    Optional<ObjectProxy> Object;
+    ASSERT_THAT_ERROR(CAS2->getProxy(ID).moveInto(Object), Succeeded());
+    ASSERT_TRUE(Object);
+    EXPECT_EQ(Content, Object->getData());
+  }
+}
+
+TEST_P(CASTest, NodesBig) {
+  std::unique_ptr<ObjectStore> CAS = createObjectStore();
+
+  // Specifically check near 1MB for objects large enough they're likely to be
+  // stored externally in an on-disk CAS, and such that one of them will be
+  // near a page boundary.
+  SmallString<0> Storage;
+  constexpr size_t InterestingSize = 1024U * 1024ULL;
+  constexpr size_t WordSize = sizeof(void *);
+
+  // Start much smaller to account for headers.
+  constexpr size_t SizeB = InterestingSize - 8 * WordSize;
+  constexpr size_t SizeE = InterestingSize + 1;
+  if (Storage.size() < SizeE)
+    Storage.resize(SizeE, '\01');
+
+  SmallVector<ObjectRef, 4> CreatedNodes;
+  // Avoid checking every size because this is an expensive test. Just check
+  // for data that is 8B-word-aligned, and one less. Also appending the created
+  // nodes as the references in the next block to check references are created
+  // correctly.
+  for (size_t Size = SizeB; Size < SizeE; Size += WordSize) {
+    for (bool IsAligned : {false, true}) {
+      StringRef Data(Storage.data(), Size - (IsAligned ? 0 : 1));
+      Optional<ObjectProxy> Node;
+      ASSERT_THAT_ERROR(CAS->createProxy(CreatedNodes, Data).moveInto(Node),
+                        Succeeded());
+      ASSERT_EQ(Data, Node->getData());
+      ASSERT_EQ(0, Node->getData().end()[0]);
+      ASSERT_EQ(Node->getNumReferences(), CreatedNodes.size());
+      CreatedNodes.emplace_back(Node->getRef());
+    }
+  }
+
+  for (auto ID : CreatedNodes)
+    ASSERT_THAT_ERROR(CAS->validate(CAS->getID(ID)), Succeeded());
+}

llvm/unittests/CMakeLists.txt

 endfunction()
 
 add_subdirectory(ADT)
 add_subdirectory(Analysis)
 add_subdirectory(AsmParser)
 add_subdirectory(BinaryFormat)
 add_subdirectory(Bitcode)
 add_subdirectory(Bitstream)
+add_subdirectory(CAS)
 add_subdirectory(CodeGen)
 add_subdirectory(DebugInfo)
 add_subdirectory(Debuginfod)
 add_subdirectory(Demangle)
 add_subdirectory(ExecutionEngine)
 add_subdirectory(FileCheck)
 add_subdirectory(Frontend)
 add_subdirectory(FuzzMutate)