src/fs/root/tree.ts
import * as cbor from "@ipld/dag-cbor"
import * as uint8arrays from "uint8arrays"
import { CID } from "multiformats/cid"
import { AddResult } from "../../ipfs/index.js"
import { BareNameFilter } from "../protocol/private/namefilter.js"
import { Puttable, SimpleLink, SimpleLinks } from "../types.js"
import { Branch, DistinctivePath } from "../../path.js"
import { Maybe, decodeCID } from "../../common/index.js"
import { Permissions } from "../../ucan/permissions.js"
import { get as getIpfs } from "../../ipfs/config.js"
import * as crypto from "../../crypto/index.js"
import * as identifiers from "../../common/identifiers.js"
import * as link from "../link.js"
import * as ipfs from "../../ipfs/index.js"
import * as pathing from "../../path.js"
import * as protocol from "../protocol/index.js"
import * as storage from "../../storage/index.js"
import * as typeChecks from "../../common/type-checks.js"
import * as ucanPermissions from "../../ucan/permissions.js"
import * as versions from "../versions.js"
import BareTree from "../bare/tree.js"
import MMPT from "../protocol/private/mmpt.js"
import PublicTree from "../v1/PublicTree.js"
import PrivateTree from "../v1/PrivateTree.js"
import PrivateFile from "../v1/PrivateFile.js"
type PrivateNode = PrivateTree | PrivateFile
export default class RootTree implements Puttable {
links: SimpleLinks
mmpt: MMPT
privateLog: Array<SimpleLink>
sharedCounter: number
sharedLinks: SimpleLinks
publicTree: PublicTree
prettyTree: BareTree
privateNodes: Record<string, PrivateNode>
constructor({ links, mmpt, privateLog, sharedCounter, sharedLinks, publicTree, prettyTree, privateNodes }: {
links: SimpleLinks
mmpt: MMPT
privateLog: Array<SimpleLink>
sharedCounter: number
sharedLinks: SimpleLinks
publicTree: PublicTree
prettyTree: BareTree
privateNodes: Record<string, PrivateNode>
}) {
this.links = links
this.mmpt = mmpt
this.privateLog = privateLog
this.sharedCounter = sharedCounter
this.sharedLinks = sharedLinks
this.publicTree = publicTree
this.prettyTree = prettyTree
this.privateNodes = privateNodes
}
// INITIALISATION
// --------------
static async empty({ rootKey }: { rootKey: string }): Promise<RootTree> {
const publicTree = await PublicTree.empty()
const prettyTree = await BareTree.empty()
const mmpt = MMPT.create()
// Private tree
const rootPath = pathing.toPosix(pathing.directory(pathing.Branch.Private))
const rootTree = await PrivateTree.create(mmpt, rootKey, null)
await rootTree.put()
// Construct tree
const tree = new RootTree({
links: {},
mmpt,
privateLog: [],
sharedCounter: 1,
sharedLinks: {},
publicTree,
prettyTree,
privateNodes: {
[rootPath]: rootTree
}
})
// Store root key
await RootTree.storeRootKey(rootKey)
// Set version and store new sub trees
await tree.setVersion(versions.latest)
await Promise.all([
tree.updatePuttable(Branch.Public, publicTree),
tree.updatePuttable(Branch.Pretty, prettyTree),
tree.updatePuttable(Branch.Private, mmpt)
])
// Fin
return tree
}
static async fromCID(
{ cid, permissions }: { cid: CID; permissions?: Permissions }
): Promise<RootTree> {
const links = await protocol.basic.getSimpleLinks(cid)
const keys = permissions ? await permissionKeys(permissions) : []
// Load public parts
const publicCID = links[Branch.Public]?.cid || null
const publicTree = publicCID === null
? await PublicTree.empty()
: await PublicTree.fromCID(decodeCID(publicCID))
const prettyTree = links[Branch.Pretty]
? await BareTree.fromCID(decodeCID(links[Branch.Pretty].cid))
: await BareTree.empty()
// Load private bits
const privateCID = links[Branch.Private]?.cid || null
let mmpt, privateNodes
if (privateCID === null) {
mmpt = MMPT.create()
privateNodes = {}
} else {
mmpt = await MMPT.fromCID(decodeCID(privateCID))
privateNodes = await loadPrivateNodes(keys, mmpt)
}
const privateLogCid = links[Branch.PrivateLog]?.cid
const privateLog = privateLogCid
? await ipfs.dagGet(decodeCID(privateLogCid))
.then(dagNode => dagNode.Links.map(link.fromDAGLink))
.then(links => links.sort((a, b) => {
return parseInt(a.name, 10) - parseInt(b.name, 10)
}))
: []
// Shared
const sharedCid = links[Branch.Shared]?.cid || null
const sharedLinks = sharedCid
? await this.getSharedLinks(decodeCID(sharedCid))
: {}
const sharedCounterCid = links[Branch.SharedCounter]?.cid || null
const sharedCounter = sharedCounterCid
? await protocol.basic
.getFile(decodeCID(sharedCounterCid))
.then(a => JSON.parse(uint8arrays.toString(a, "utf8")))
: 1
// Construct tree
const tree = new RootTree({
links,
mmpt,
privateLog,
sharedCounter,
sharedLinks,
publicTree,
prettyTree,
privateNodes
})
if (links[Branch.Version] == null) {
// Old versions of WNFS didn't write a root version link
await tree.setVersion(versions.latest)
}
// Fin
return tree
}
// MUTATIONS
// ---------
async put(): Promise<CID> {
const { cid } = await this.putDetailed()
return cid
}
async putDetailed(): Promise<AddResult> {
return protocol.basic.putLinks(this.links)
}
updateLink(name: string, result: AddResult): this {
const { cid, size, isFile } = result
this.links[name] = link.make(name, cid, isFile, size)
return this
}
async updatePuttable(name: string, puttable: Puttable): Promise<this> {
return this.updateLink(name, await puttable.putDetailed())
}
// PRIVATE TREES
// -------------
static async storeRootKey(rootKey: string): Promise<void> {
const path = pathing.directory(pathing.Branch.Private)
const rootKeyId = await identifiers.readKey({ path })
await crypto.keystore.importSymmKey(rootKey, rootKeyId)
}
static async retrieveRootKey(): Promise<string> {
const path = pathing.directory(pathing.Branch.Private)
const rootKeyId = await identifiers.readKey({ path })
return await crypto.keystore.exportSymmKey(rootKeyId)
}
findPrivateNode(path: DistinctivePath): [DistinctivePath, PrivateNode | null] {
return findPrivateNode(this.privateNodes, path)
}
// PRIVATE LOG
// -----------
// CBOR array containing chunks.
//
// Chunk size is based on the default IPFS block size,
// which is 1024 * 256 bytes. 1 log chunk should fit in 1 block.
// We'll use the CSV format for the data in the chunks.
static LOG_CHUNK_SIZE = 1020 // Math.floor((1024 * 256) / (256 + 1))
async addPrivateLogEntry(cid: CID): Promise<void> {
const log = [...this.privateLog]
let idx = Math.max(0, log.length - 1)
// get last chunk
let lastChunk = log[idx]?.cid
? (await ipfs.cat(decodeCID(log[idx].cid))).split(",")
: []
// needs new chunk
const needsNewChunk = lastChunk.length + 1 > RootTree.LOG_CHUNK_SIZE
if (needsNewChunk) {
idx = idx + 1
lastChunk = []
}
// add to chunk
const hashedCid = await crypto.hash.sha256Str(cid.toString())
const updatedChunk = [...lastChunk, hashedCid]
const updatedChunkDeposit = await protocol.basic.putFile(
updatedChunk.join(",")
)
log[idx] = {
name: idx.toString(),
cid: updatedChunkDeposit.cid,
size: updatedChunkDeposit.size
}
// save log
const logDeposit = await ipfs.dagPutLinks(
log.map(link.toDAGLink)
)
this.updateLink(Branch.PrivateLog, {
cid: logDeposit.cid,
isFile: false,
size: await ipfs.size(logDeposit.cid)
})
this.privateLog = log
}
// SHARING
// -------
async addShares(links: SimpleLink[]): Promise<this> {
this.sharedLinks = links.reduce(
(acc, link) => ({ ...acc, [link.name]: link }),
this.sharedLinks
)
const cborApprovedLinks = Object.values(this.sharedLinks).reduce(
(acc, { cid, name, size }) => ({ ...acc,
[name]: { cid, name, size }
}),
{}
)
const ipfsClient = await getIpfs()
const cid = await ipfsClient.block.put(
cbor.encode(cborApprovedLinks),
{ format: cbor.name, mhtype: "sha2-256", pin: false, version: 1 }
)
this.updateLink(Branch.Shared, {
cid: cid,
isFile: false,
size: await ipfs.size(cid)
})
return this
}
static async getSharedLinks(cid: CID): Promise<SimpleLinks> {
const ipfsClient = await getIpfs()
const block = await ipfsClient.block.get(cid)
const decodedBlock = cbor.decode(block)
if (!typeChecks.isObject(decodedBlock)) throw new Error("Invalid shared section, not an object")
return Object.values(decodedBlock).reduce(
(acc: SimpleLinks, link: unknown): SimpleLinks => {
if (!typeChecks.isObject(link)) return acc
const name = link.name ? link.name as string : null
const cid = link.cid
? decodeCID(link.cid as any)
: null
if (!name || !cid) return acc
return { ...acc, [name]: { name, cid, size: (link.size || 0) as number } }
},
{}
)
}
async setSharedCounter(counter: number): Promise<number> {
this.sharedCounter = counter
const { cid, size } = await protocol.basic.putFile(
JSON.stringify(counter)
)
this.updateLink(Branch.SharedCounter, {
cid: cid,
isFile: true,
size: size
})
return counter
}
async bumpSharedCounter(): Promise<number> {
const newCounter = this.sharedCounter + 1
return this.setSharedCounter(newCounter)
}
// VERSION
// -------
async setVersion(v: versions.SemVer): Promise<this> {
const result = await protocol.basic.putFile(versions.toString(v))
return this.updateLink(Branch.Version, result)
}
async getVersion(): Promise<versions.SemVer | null> {
const file = await protocol.basic.getFile(decodeCID(this.links[Branch.Version].cid))
return versions.fromString(uint8arrays.toString(file))
}
}
// ㊙️
type PathKey = { path: DistinctivePath; key: string }
async function findBareNameFilter(
map: Record<string, PrivateNode>,
path: DistinctivePath
): Promise<Maybe<BareNameFilter>> {
const bareNameFilterId = await identifiers.bareNameFilter({ path })
const bareNameFilter: Maybe<BareNameFilter> = await storage.getItem(bareNameFilterId)
if (bareNameFilter) return bareNameFilter
const [nodePath, node] = findPrivateNode(map, path)
if (!node) return null
const unwrappedPath = pathing.unwrap(path)
const relativePath = unwrappedPath.slice(pathing.unwrap(nodePath).length)
if (PrivateFile.instanceOf(node)) {
return relativePath.length === 0 ? node.header.bareNameFilter : null
}
if (!node.exists(relativePath)) {
if (pathing.isDirectory(path)) await node.mkdir(relativePath)
else await node.add(relativePath, "")
}
return node.get(relativePath).then(t => t ? t.header.bareNameFilter : null)
}
function findPrivateNode(
map: Record<string, PrivateNode>,
path: DistinctivePath
): [DistinctivePath, PrivateNode | null] {
const t = map[pathing.toPosix(path)]
if (t) return [ path, t ]
const parent = pathing.parent(path)
return parent
? findPrivateNode(map, parent)
: [ path, null ]
}
function loadPrivateNodes(
pathKeys: PathKey[],
mmpt: MMPT
): Promise<Record<string, PrivateNode>> {
return sortedPathKeys(pathKeys).reduce((acc, { path, key }) => {
return acc.then(async map => {
let privateNode
const unwrappedPath = pathing.unwrap(path)
// if root, no need for bare name filter
if (unwrappedPath.length === 1 && unwrappedPath[0] === pathing.Branch.Private) {
privateNode = await PrivateTree.fromBaseKey(mmpt, key)
} else {
const bareNameFilter = await findBareNameFilter(map, path)
if (!bareNameFilter) throw new Error(`Was trying to load the PrivateTree for the path \`${path}\`, but couldn't find the bare name filter for it.`)
if (pathing.isDirectory(path)) {
privateNode = await PrivateTree.fromBareNameFilter(mmpt, bareNameFilter, key)
} else {
privateNode = await PrivateFile.fromBareNameFilter(mmpt, bareNameFilter, key)
}
}
const posixPath = pathing.toPosix(path)
return { ...map, [posixPath]: privateNode }
})
}, Promise.resolve({}))
}
async function permissionKeys(
permissions: Permissions
): Promise<PathKey[]> {
return ucanPermissions.paths(permissions).reduce(async (
acc: Promise<PathKey[]>,
path: DistinctivePath
): Promise<PathKey[]> => {
if (pathing.isBranch(pathing.Branch.Public, path)) return acc
const name = await identifiers.readKey({ path })
const key = await crypto.keystore.exportSymmKey(name)
const pk: PathKey = { path: path, key: key }
return acc.then(
list => [ ...list, pk ]
)
}, Promise.resolve(
[]
))
}
/**
* Sort keys alphabetically by path.
* This is used to sort paths by parent first.
*/
function sortedPathKeys(list: PathKey[]): PathKey[] {
return list.sort(
(a, b) => pathing.toPosix(a.path).localeCompare(pathing.toPosix(b.path))
)
}