Goals:

  • Handcode AIPW Double ML for ATE

  • Compare partially linear and AIPW Double ML for ATE

  • See how partially linear model can go wrong if effects are actually heterogeneous


Effect homogeneity

DGP

Consider the following DGP with homogeneous effects and a binary treatment:

  • \(p=5\) independent covariates \(X_1,...,X_k,...,X_{5}\) drawn from a uniform distribution: \(X_k \sim uniform(-\pi,\pi)\)

  • The treatment model is \(W \sim Bernoulli(\underbrace{\Phi(sin(X_1))}_{e(X)})\), where \(\Phi(\cdot)\) is the standard normal cumulative density function

  • The outcome model is \(Y = \underbrace{0.1}_{\tau} W + \underbrace{sin(X_1)}_{m(X)}+ \varepsilon\), with \(\varepsilon \sim N(0,1)\)

This means that we are in a highly nonlinear setting, but only one variable (\(X_1\)) is relevant and the others are just noise. The treatment model produces in expectation a balanced treatment share with 50% controls and 50% treated.

if (!require("grf")) install.packages("grf", dependencies = TRUE); library(grf)
if (!require("tidyverse")) install.packages("tidyverse", dependencies = TRUE); library(tidyverse)
if (!require("patchwork")) install.packages("patchwork", dependencies = TRUE); library(patchwork)
if (!require("causalDML")) {
  if (!require("devtools")) install.packages("devtools", dependencies = TRUE); library(devtools)
  install_github(repo="MCKnaus/causalDML") 
}; library(causalDML)

set.seed(1234)

# Set parameters
n = 200
p = 10
theta = 0.1

# Define and plot functions
x = matrix(runif(n*p,-pi,pi),ncol=p)
e = function(x){pnorm(sin(x))}
m0 = function(x){sin(x)}
m1 = function(x){m0(x) + theta}
tau = function(x){m1(x) - m0(x)}
w = rbinom(n,1,e(x[,1]))
y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)

g1 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=e,size=1) + ylab("e") + xlab("X1")
g2 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,aes(colour="Y1")) + 
  stat_function(fun=m0,size=1,aes(colour="Y0")) + ylab("Y") + xlab("X1")
g3 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab(expression(tau)) + xlab("X1")
g1 / g2 / g3


Hand-coded AIPW w/o cross-fitting

We draw a sample of \(N=200\) and estimate the nuisance parameters \(e(X)=E[W|X]\), \(m(0,X)=E[Y|W=0,X]\) and \(m(1,X)=E[Y|W=1,X]\) using random forest without honesty (sample size too small for honesty) and plug the predictions into the pseudo outcome: \[\tilde{Y}_{ATE} = \underbrace{\hat{m}(1,X) - \hat{m}(0,X)}_{\text{outcome predictions}} + \underbrace{\frac{W (Y - \hat{m}(1,X))}{\hat{e}(X)} - \frac{(1-W) (Y - \hat{m}(0,X))}{1-\hat{e}(X)}}_{\text{weighted residuals}}\]

# No cross-fitting
# Predict propensity score
rf = regression_forest(x,w,honesty=F)
ehat = predict(rf,newdata=x)$predictions
# Model control outcome using only control and predict for all
rf = regression_forest(x[w==0,],y[w==0],honesty=F)
m0hat = predict(rf,newdata=x)$predictions
# Model control outcome using only control and predict for all
rf = regression_forest(x[w==1,],y[w==1],honesty=F)
m1hat = predict(rf,newdata=x)$predictions
# Generate pseudo-outcome
pseudo_y =  m1hat - m0hat +
            w*(y-m1hat) / ehat - (1-w)*(y-m0hat) / (1-ehat)

Take the mean of the pseudo-outcome and run a t-test

mean(pseudo_y)
[1] 0.1179403
t.test(pseudo_y)

    One Sample t-test

data:  pseudo_y
t = 1.3308, df = 199, p-value = 0.1848
alternative hypothesis: true mean is not equal to 0
95 percent confidence interval:
 -0.05681688  0.29269743
sample estimates:
mean of x 
0.1179403 

or run just an OLS regression with only a constant for point estimation and inference in one step.

summary(lm(pseudo_y~1))

Call:
lm(formula = pseudo_y ~ 1)

Residuals:
    Min      1Q  Median      3Q     Max 
-4.1751 -0.8027 -0.0574  0.8494  3.3141 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)
(Intercept)  0.11794    0.08862   1.331    0.185

Residual standard error: 1.253 on 199 degrees of freedom


Hand-coded AIPW with 2-fold cross-fitting

The theoretical results require that we predict the nuisance parameters out-of-sample. The easiest way to do this is two-fold cross-fitting:

  • Split the sample in two random subsamples, S1 and S2

  • Form prediction models in S1, use it to predict in S2

  • Form prediction models in S2, use it to predict in S1

  • Plug the prediction in the pseudo-outcome and proceed as above

# 2-fold cross-fitting
m0hat = m1hat = ehat = rep(NA,n)
# Draw random indices for sample 1
index_s1 = sample(1:n,n/2)
# Create S1
x1 = x[index_s1,]
w1 = w[index_s1]
y1 = y[index_s1]
# Create sample 2 with those not in S1
x2 = x[-index_s1,]
w2 = w[-index_s1]
y2 = y[-index_s1]
# Model in S1, predict in S2
rf = regression_forest(x1,w1,honesty=F)
ehat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x1[w1==0,],y1[w1==0],honesty=F)
m0hat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x1[w1==1,],y1[w1==1],honesty=F)
m1hat[-index_s1] = predict(rf,newdata=x2)$predictions
# Model in S2, predict in S1
rf = regression_forest(x2,w2,honesty=F)
ehat[index_s1] = predict(rf,newdata=x1)$predictions
rf = regression_forest(x2[w2==0,],y2[w2==0],honesty=F)
m0hat[index_s1] = predict(rf,newdata=x1)$predictions
rf = regression_forest(x2[w2==1,],y2[w2==1],honesty=F)
m1hat[index_s1] = predict(rf,newdata=x1)$predictions
# Generate pseudo-outcome and take and test mean
pseudo_y =  m1hat - m0hat +
  w*(y-m1hat) / ehat - (1-w)*(y-m0hat) / (1-ehat)
summary(lm(pseudo_y ~ 1))

Call:
lm(formula = pseudo_y ~ 1)

Residuals:
     Min       1Q   Median       3Q      Max 
-28.3108  -0.6695   0.2376   1.4207   9.9140 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)
(Intercept)  0.01853    0.22297   0.083    0.934

Residual standard error: 3.153 on 199 degrees of freedom


AIPW with 5-fold cross-fitting

2-fold cross-fitting is easy to implement but especially in small sample sizes using only 50% of the data to estimate the nuisance parameters might lead to unstable predictions.

Thus, we use the DML_aipw function of the causalDML package to run 5-fold cross-fitting. This package requires to create the methods that we use because it allows for ensemble methods. For now, we focus on the honest random forest.

With 5-fold cross-fitting, we split the sample in 5 folds and use 4 folds (80% of the data) to predict the left out fold (20% of the data). We iterate such that every fold is left out once.

# 5-fold cross-fitting with causalDML package
# Create learner
forest = create_method("forest_grf",args=list(honesty=F))
# Run and 
aipw = DML_aipw(y,w,x,ml_w=list(forest),ml_y=list(forest),cf=5)
summary(aipw$APO)
         APO        SE
0 0.01579749 0.1498814
1 0.13913183 0.1668602

We observe two things:

  • The estimator with 5-fold cross-fitting comes closest to the true value

  • However, without cross-fitting is also close, but with a much much smaller standard error.

Let’s see whether the former is only by chance or systematic, and especially whether the latter is too good to be true.


Simulation study homogeneous effect setting

We run a simulation study drawing \(M=1,000\) samples from the DGP described above and estimate the effect with three different estimators:

  • Partially linear model estimated with 5-fold cross-fitting

  • AIPW without cross-fitting

  • AIPW with 5-fold cross-fitting

Additionally to bias, variance and MSE, we also check the quality of the standard errors via the coverage rate. The coverage rate checks how often the true value is included in the confidence intervals (see ring toss analogy as an intuitive refresher).

We would like to have nominal coverage, i.e. for a 95% confidence level it should happen in 95% of the replications, for a 90% confidence level in 90% of the replications, …

# set number of replications
n_rep = 1000 # Decrease for faster computation
# initialize storage for results
coverage = results = matrix(NA,n_rep,3)
colnames(coverage) = colnames(results) = c("PL cf5","AIPW no","AIPW cf5")

# start the simulation
for (i in 1:n_rep) {
  x = matrix(runif(n*p,-pi,pi),ncol=p)
  w = rbinom(n,1,e(x[,1]))
  y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)
  
  # partially linear model
  pl = DML_partial_linear(y,w,x,ml_w=list(forest),ml_y=list(forest),cf=5)
  results[i,1] = pl$result[1]
  coverage[i,1] = (pl$result[1] - 1.96*pl$result[2] < theta & pl$result[1] + 1.96*pl$result[2] > theta)
  
  # No cross-fitting
  rf = regression_forest(x,w,honesty=F)
  ehat = predict(rf,newdata=x)$predictions
  rf = regression_forest(x[w==0,],y[w==0],honesty=F)
  m0hat = predict(rf,newdata=x)$predictions
  rf = regression_forest(x[w==1,],y[w==1],honesty=F)
  m1hat = predict(rf,newdata=x)$predictions
  pseudo_y =  m1hat - m0hat +
    w*(y-m1hat) / ehat - (1-w)*(y-m0hat) / (1-ehat)
  results[i,2] = mean(pseudo_y)
  tt = t.test(pseudo_y)
  coverage[i,2] = (tt$conf.int[1]  < theta & tt$conf.int[2] > theta)

  # 5-fold cross-fitting with causalDML package reusing the folds and pscores of PL
  aipw = DML_aipw(y,w,x,ml_y=list(forest),cf=5,
                  e_mat = cbind(1-pl$e_hat,pl$e_hat),cf_mat = pl$cf_mat)
  results[i,3] = aipw$ATE$results[1]
  coverage[i,3] = (aipw$ATE$results[1] - 1.96*aipw$ATE$results[2] < theta & aipw$ATE$results[1] + 1.96*aipw$ATE$results[2] > theta)
}

We plot the estimator distributions and note that the estimator without cross-fitting seems to be biased:

as.data.frame(results) %>% pivot_longer(cols=everything(),names_to = "Estimator",values_to = "coef") %>%
  ggplot(aes(x = coef, fill = Estimator)) + geom_density(alpha=0.5) + theme_bw() + geom_vline(xintercept=theta)

This is confirmed by the decomposition of the MSE (see formula in SNB_Partially_linear notebook):

data.frame(method = colnames(results),
           bias2 = colMeans(results-theta)^2,
           var = colMeans(sweep(results,2,colMeans(results))^2)) %>% 
  pivot_longer(-method,names_to = "Component",values_to = "MSE") %>%
  ggplot(aes(fill=factor(Component,levels=c("var","bias2")), y=MSE, x=method)) + 
  geom_bar(position="stack", stat="identity") + scale_fill_discrete(name = "Component")

Notably the variance of the partially linear estimator is smaller compared to cross-fitted AIPW, while both are basically unbiased. This makes sense because we looked at the case with actual effect homogeneity, where the partially linear estimator is an efficient estimator in case of homoscedastic errors, which we impose.

Finally, let’s check the coverage rate:

data.frame(method = colnames(results),
           coverage = colMeans(coverage)) %>% 
  ggplot(aes(y=coverage, x=method)) + geom_hline(yintercept=0.95,linetype="dashed") + 
  geom_point(size=5,shape=4) + scale_fill_discrete(name = "Component") + ylim(c(0,1)) +
  geom_hline(yintercept=c(0,1))

Without cross-fitting, the coverage rate of AIPW is only 50%, which reflects the bias and that the estimated standard errors are too small. The other two slightly undercover, but especially cross-fitted AIPW works well in terms of inference.



Effect heterogeneity with balanced treatment shares

DGP

Now we introduce heterogeneous treatment effects leaving the rest unchanged:

  • \(p=10\) independent covariates \(X_1,...,X_k,...,X_{10}\) drawn from a uniform distribution: \(X_k \sim uniform(-\pi,\pi)\)

  • The treatment model is \(W \sim Bernoulli(\underbrace{\Phi(sin(X_1))}_{e(X)})\), where \(\Phi(\cdot)\) is the standard normal cumulative density function

  • The outcome model of the treated is \(Y(1) = \underbrace{sin(X_1)}_{m_1(X)}+ \varepsilon\), with \(\varepsilon \sim N(0,1)\)

  • The outcome model of the controls is \(Y(0) = \underbrace{cos(X_1+1/2\pi)}_{m_0(X)}+ \varepsilon\), with \(\varepsilon \sim N(0,1)\)

This means that the ATE is equal to zero (\(\tau_{ATE}=0\)) but we have tremendous effect heterogeneity:

x = matrix(runif(n*p,-pi,pi),ncol=p)
e = function(x){pnorm(sin(x))}
m1 = function(x){sin(x)}
m0 = function(x){cos(x+1/2*pi)}
tau = function(x){m1(x) - m0(x)}
w = rbinom(n,1,e(x[,1]))
y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)

g1 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=e,size=1) + ylab("e") + xlab("X1")
g2 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,aes(colour="Y1")) + 
  stat_function(fun=m0,size=1,aes(colour="Y0")) + ylab("Y") + xlab("X1")
g3 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab(expression(tau)) + xlab("X1")
g1 / g2 / g3


Simulation study heterogeneous effect setting

We run a simulation study drawing \(M=1,000\) samples from the DGP described above and estimate the effect with three different estimators:

  • Partially linear model estimated with 5-fold cross-fitting

  • AIPW without cross-fitting

  • AIPW with 5-fold cross-fitting

# initialize storage for results
coverage_het = results_het = matrix(NA,n_rep,3)
colnames(coverage_het) = colnames(results_het) = c("PL cf5","AIPW no","AIPW cf5")

# start the simulation
for (i in 1:n_rep) {
  x = matrix(runif(n*p,-pi,pi),ncol=p)
  w = rbinom(n,1,e(x[,1]))
  y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)
  
  # partially linear model
  pl = DML_partial_linear(y,w,x,ml_w=list(forest),ml_y=list(forest),cf=5)
  results_het[i,1] = pl$result[1]
  coverage_het[i,1] = (pl$result[1] - 1.96*pl$result[2] < 0 & pl$result[1] + 1.96*pl$result[2] > 0)
  
  # No cross-fitting
  rf = regression_forest(x,w,honesty=F)
  ehat = predict(rf,newdata=x)$predictions
  rf = regression_forest(x[w==0,],y[w==0],honesty=F)
  m0hat = predict(rf,newdata=x)$predictions
  rf = regression_forest(x[w==1,],y[w==1],honesty=F)
  m1hat = predict(rf,newdata=x)$predictions
  pseudo_y =  m1hat - m0hat +
    w*(y-m1hat) / ehat - (1-w)*(y-m0hat) / (1-ehat)
  results_het[i,2] = mean(pseudo_y)
  tt = t.test(pseudo_y)
  coverage_het[i,2] = (tt$conf.int[1]  < 0 & tt$conf.int[2] > 0)
  
  aipw = DML_aipw(y,w,x,ml_y=list(forest),cf=5,
                  e_mat = cbind(1-pl$e_hat,pl$e_hat),cf_mat = pl$cf_mat)
  results_het[i,3] = aipw$ATE$results[1]
  coverage_het[i,3] = (aipw$ATE$results[1] - 1.96*aipw$ATE$results[2] < 0 & aipw$ATE$results[1] + 1.96*aipw$ATE$results[2] > 0)
}

We plot the estimator distributions and note that basically all estimators are unbiased:

as.data.frame(results_het) %>% pivot_longer(cols=everything(),names_to = "Estimator",values_to = "coef") %>%
  ggplot(aes(x = coef, fill = Estimator)) + geom_density(alpha=0.5) + theme_bw() + geom_vline(xintercept=0)

This is confirmed by the decomposition of the MSE:

data.frame(method = colnames(results_het),
           bias2 = colMeans(results_het-0)^2,
           var = colMeans(sweep(results_het,2,colMeans(results_het))^2)) %>% 
  pivot_longer(-method,names_to = "Component",values_to = "MSE") %>%
  ggplot(aes(fill=factor(Component,levels=c("var","bias2")), y=MSE, x=method)) + 
  geom_bar(position="stack", stat="identity") + scale_fill_discrete(name = "Component")

Notably the partially linear estimator is unbiased although it assumes effect heterogeneity. However, it shows a higher variance than the AIPW estimator. This is not unexpected because AIPW is an efficient estimator in the heterogeneous effects setting. But cross-fitting seems to be harmful as we have no bias and lower variance without all this additional effort.

BUT, let’s check the coverage rate:

data.frame(method = colnames(results_het),
           coverage = colMeans(coverage_het)) %>% 
  ggplot(aes(y=coverage, x=method)) + geom_hline(yintercept=0.95,linetype="dashed") + 
  geom_point(size=5,shape=4) + scale_fill_discrete(name = "Component") + ylim(c(0,1)) +
  geom_hline(yintercept=c(0,1))

Cross-fitted AIPW shows nearly perfect coverage, while the standard errors without cross-fitting are much too small.

\(\Rightarrow\) Cross-fitting is not necessarily required to remove bias in the point estimates due to overfitting, but to remove downward bias in the standard errors. The true ATE is zero in our case, but we would find significant effects in about 20% of the cases instead of the 5% that we allow to happen given our confidence level.



Effect heterogeneity with unbalanced treatment shares

DGP

Now we introduce unbalanced treatment shares leaving the rest unchanged:

  • \(p=10\) independent covariates \(X_1,...,X_k,...,X_{10}\) drawn from a uniform distribution: \(X_k \sim uniform(-\pi,\pi)\)

  • The treatment model is \(W \sim Bernoulli(\underbrace{\Phi(sin(X_1-0.5))}_{e(X)})\), where \(\Phi(\cdot)\) is the standard normal cumulative density function

  • The outcome model of the treated is \(Y(1) = \underbrace{sin(X_1)}_{m_1(X)}+ \varepsilon\), with \(\varepsilon \sim N(0,1)\)

  • The outcome model of the controls is \(Y(0) = \underbrace{cos(X_1+1/2\pi)}_{m_0(X)}+ \varepsilon\), with \(\varepsilon \sim N(0,1)\)

We now expect roughly 1/3 treated and increase the sample size to 300 such that at least 100 observations are in each treatment arm:

n = 300

x = matrix(runif(n*p,-pi,pi),ncol=p)
e = function(x){pnorm(sin(x)-0.5)}
m1 = function(x){sin(x)}
m0 = function(x){cos(x+1/2*pi)}
tau = function(x){m1(x) - m0(x)}
w = rbinom(n,1,e(x[,1]))
y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)

g1 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=e,size=1) + ylab("e") + xlab("X1")
g2 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,aes(colour="Y1")) + 
  stat_function(fun=m0,size=1,aes(colour="Y0")) + ylab("Y") + xlab("X1")
g3 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab(expression(tau)) + xlab("X1")
g1 / g2 / g3


Simulation study unbalanced treatment shares

We run a simulation study drawing \(M=1,000\) samples from the DGP described above and estimate the effect with three different estimators:

  • Partially linear model estimated with 5-fold cross-fitting

  • AIPW without cross-fitting

  • AIPW with 5-fold cross-fitting

# initialize storage for results
coverage_unbal = results_unbal = matrix(NA,n_rep,3)
colnames(coverage_unbal) = colnames(results_unbal) = c("PL cf5","AIPW no","AIPW cf5")

# start simulation
for (i in 1:n_rep) {
  x = matrix(runif(n*p,-pi,pi),ncol=p)
  w = rbinom(n,1,e(x[,1]))
  y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)
  
  # partially linear model
  pl = DML_partial_linear(y,w,x,ml_w=list(forest),ml_y=list(forest),cf=5)
  results_unbal[i,1] = pl$result[1]
  coverage_unbal[i,1] = (pl$result[1] - 1.96*pl$result[2] < 0 & pl$result[1] + 1.96*pl$result[2] > 0)
  
  # No cross-fitting
  rf = regression_forest(x,w,honesty=F)
  ehat = predict(rf,newdata=x)$predictions
  rf = regression_forest(x[w==0,],y[w==0],honesty=F)
  m0hat = predict(rf,newdata=x)$predictions
  rf = regression_forest(x[w==1,],y[w==1],honesty=F)
  m1hat = predict(rf,newdata=x)$predictions
  pseudo_y =  m1hat - m0hat +
    w*(y-m1hat) / ehat - (1-w)*(y-m0hat) / (1-ehat)
  results_unbal[i,2] = mean(pseudo_y)
  tt = t.test(pseudo_y)
  coverage_unbal[i,2] = (tt$conf.int[1]  < 0 & tt$conf.int[2] > 0)
  
  # 5-fold cross-fitting with causalDML package reusing the folds and pscores of PL
  aipw = DML_aipw(y,w,x,ml_y=list(forest),cf=5,
                  e_mat = cbind(1-pl$e_hat,pl$e_hat),cf_mat = pl$cf_mat)
  results_unbal[i,3] = aipw$ATE$results[1]
  coverage_unbal[i,3] = (aipw$ATE$results[1] - 1.96*aipw$ATE$results[2] < 0 & aipw$ATE$results[1] + 1.96*aipw$ATE$results[2] > 0)
}

We plot the estimator distributions:

as.data.frame(results_unbal) %>% pivot_longer(cols=everything(),names_to = "Estimator",values_to = "coef") %>%
  ggplot(aes(x = coef, fill = Estimator)) + geom_density(alpha=0.5) + theme_bw() + geom_vline(xintercept=0)

BOOM!!! Maybe you thought that the effect homogeneity assumption imposed by the partially linear model was harmless given that it worked nicely above, but the 50-50 treatment share is just nice in this regard (see Słoczyński (2020) for a nice discussion in case of OLS). In the presence of heterogeneous effects, estimators assuming effect homogeneity estimate some causal effect, but not necessarily the ATE. The estimator distribution centers nicely around 0.5, while we know it should center around zero.

This is confirmed by the decomposition of the MSE showing a huge bias:

data.frame(method = colnames(results_unbal),
           bias2 = colMeans(results_unbal-0,na.rm=T)^2,
           var = colMeans(sweep(results_unbal,2,colMeans(results_unbal,na.rm=T))^2,na.rm=T)) %>% 
  pivot_longer(-method,names_to = "Component",values_to = "MSE") %>%
  ggplot(aes(fill=factor(Component,levels=c("var","bias2")), y=MSE, x=method)) + 
  geom_bar(position="stack", stat="identity") + scale_fill_discrete(name = "Component")

This kills of course also the coverage rate:

data.frame(method = colnames(results_unbal),
           coverage = colMeans(coverage_unbal,na.rm=T)) %>% 
  ggplot(aes(y=coverage, x=method)) + geom_hline(yintercept=0.95,linetype="dashed") + 
  geom_point(size=5,shape=4) + scale_fill_discrete(name = "Component") + ylim(c(0,1)) +
  geom_hline(yintercept=c(0,1))

\(\Rightarrow\) We would reject the Null of \(\tau_{ATE}=0\), which is true in our setting, in 80% of the cases if we imposed the assumption of effect homogeneity.



Take-away

  • We can program a cross-fit Double ML AIPW estimator with few lines of code

  • Cross-fitting makes a difference, especially when it comes to inference

  • Estimators assuming effect homogeneity can dramatically break down in the presence of heterogeneity



Suggestions to play with the toy model

The whole thing ran several hours on my laptop, so you should decrease n_rep for the first play and then run it over night with more.

Some suggestions:

  • Let the treatment shares go e.g. from 10% to 90% in 10% steps and watch how you can basically get every effect you like with the partially linear model

  • Modify DGP (increase theta, correlation of covariates, coefficients, noise term, …)

  • Increase the number of observations

  • Increase cross-fitting folds to 10 and/or 20

LS0tDQp0aXRsZTogIkNhdXNhbCBNTDogQUlQVyBEb3VibGUgTUwgKEFURSkiDQpzdWJ0aXRsZTogIlNpbXVsYXRpb24gbm90ZWJvb2siDQphdXRob3I6ICJNaWNoYWVsIEtuYXVzIg0KZGF0ZTogImByIGZvcm1hdChTeXMudGltZSgpLCAnJW0vJXknKWAiDQpvdXRwdXQ6IA0KICBodG1sX25vdGVib29rOg0KICAgIHRvYzogdHJ1ZQ0KICAgIHRvY19mbG9hdDogdHJ1ZQ0KICAgIGNvZGVfZm9sZGluZzogc2hvdw0KLS0tDQoNCg0KR29hbHM6DQoNCi0gSGFuZGNvZGUgQUlQVyBEb3VibGUgTUwgZm9yIEFURQ0KDQotIENvbXBhcmUgcGFydGlhbGx5IGxpbmVhciBhbmQgQUlQVyBEb3VibGUgTUwgZm9yIEFURQ0KDQotIFNlZSBob3cgcGFydGlhbGx5IGxpbmVhciBtb2RlbCBjYW4gZ28gd3JvbmcgaWYgZWZmZWN0cyBhcmUgYWN0dWFsbHkgaGV0ZXJvZ2VuZW91cw0KDQo8YnI+DQoNCg0KIyBFZmZlY3QgaG9tb2dlbmVpdHkNCg0KIyMgREdQDQoNCkNvbnNpZGVyIHRoZSBmb2xsb3dpbmcgREdQIHdpdGggaG9tb2dlbmVvdXMgZWZmZWN0cyBhbmQgYSBiaW5hcnkgdHJlYXRtZW50Og0KDQotICRwPTUkIGluZGVwZW5kZW50IGNvdmFyaWF0ZXMgJFhfMSwuLi4sWF9rLC4uLixYX3s1fSQgZHJhd24gZnJvbSBhIHVuaWZvcm0gZGlzdHJpYnV0aW9uOiAkWF9rIFxzaW0gdW5pZm9ybSgtXHBpLFxwaSkkDQoNCi0gVGhlIHRyZWF0bWVudCBtb2RlbCBpcyAkVyBcc2ltIEJlcm5vdWxsaShcdW5kZXJicmFjZXtcUGhpKHNpbihYXzEpKX1fe2UoWCl9KSQsIHdoZXJlICRcUGhpKFxjZG90KSQgaXMgdGhlIHN0YW5kYXJkIG5vcm1hbCBjdW11bGF0aXZlIGRlbnNpdHkgZnVuY3Rpb24NCg0KLSBUaGUgb3V0Y29tZSBtb2RlbCBpcyAkWSA9IFx1bmRlcmJyYWNlezAuMX1fe1x0YXV9IFcgKyBcdW5kZXJicmFjZXtzaW4oWF8xKX1fe20oWCl9KyBcdmFyZXBzaWxvbiQsIHdpdGggJFx2YXJlcHNpbG9uIFxzaW0gTigwLDEpJA0KDQpUaGlzIG1lYW5zIHRoYXQgd2UgYXJlIGluIGEgaGlnaGx5IG5vbmxpbmVhciBzZXR0aW5nLCBidXQgb25seSBvbmUgdmFyaWFibGUgKCRYXzEkKSBpcyByZWxldmFudCBhbmQgdGhlIG90aGVycyBhcmUganVzdCBub2lzZS4gVGhlIHRyZWF0bWVudCBtb2RlbCBwcm9kdWNlcyBpbiBleHBlY3RhdGlvbiBhIGJhbGFuY2VkIHRyZWF0bWVudCBzaGFyZSB3aXRoIDUwJSBjb250cm9scyBhbmQgNTAlIHRyZWF0ZWQuDQoNCg0KYGBge3IsIHdhcm5pbmcgPSBGLCBtZXNzYWdlID0gRn0NCmlmICghcmVxdWlyZSgiZ3JmIikpIGluc3RhbGwucGFja2FnZXMoImdyZiIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KGdyZikNCmlmICghcmVxdWlyZSgidGlkeXZlcnNlIikpIGluc3RhbGwucGFja2FnZXMoInRpZHl2ZXJzZSIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KHRpZHl2ZXJzZSkNCmlmICghcmVxdWlyZSgicGF0Y2h3b3JrIikpIGluc3RhbGwucGFja2FnZXMoInBhdGNod29yayIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KHBhdGNod29yaykNCmlmICghcmVxdWlyZSgiY2F1c2FsRE1MIikpIHsNCiAgaWYgKCFyZXF1aXJlKCJkZXZ0b29scyIpKSBpbnN0YWxsLnBhY2thZ2VzKCJkZXZ0b29scyIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KGRldnRvb2xzKQ0KICBpbnN0YWxsX2dpdGh1YihyZXBvPSJNQ0tuYXVzL2NhdXNhbERNTCIpIA0KfTsgbGlicmFyeShjYXVzYWxETUwpDQoNCnNldC5zZWVkKDEyMzQpDQoNCiMgU2V0IHBhcmFtZXRlcnMNCm4gPSAyMDANCnAgPSAxMA0KdGhldGEgPSAwLjENCg0KIyBEZWZpbmUgYW5kIHBsb3QgZnVuY3Rpb25zDQp4ID0gbWF0cml4KHJ1bmlmKG4qcCwtcGkscGkpLG5jb2w9cCkNCmUgPSBmdW5jdGlvbih4KXtwbm9ybShzaW4oeCkpfQ0KbTAgPSBmdW5jdGlvbih4KXtzaW4oeCl9DQptMSA9IGZ1bmN0aW9uKHgpe20wKHgpICsgdGhldGF9DQp0YXUgPSBmdW5jdGlvbih4KXttMSh4KSAtIG0wKHgpfQ0KdyA9IHJiaW5vbShuLDEsZSh4WywxXSkpDQp5ID0gdyptMSh4WywxXSkgKyAoMS13KSptMCh4WywxXSkgKyBybm9ybShuLDAsMSkNCg0KZzEgPSBkYXRhLmZyYW1lKHggPSBjKC1waSwgcGkpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1lLHNpemU9MSkgKyB5bGFiKCJlIikgKyB4bGFiKCJYMSIpDQpnMiA9IGRhdGEuZnJhbWUoeCA9IGMoLXBpLCBwaSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPW0xLHNpemU9MSxhZXMoY29sb3VyPSJZMSIpKSArIA0KICBzdGF0X2Z1bmN0aW9uKGZ1bj1tMCxzaXplPTEsYWVzKGNvbG91cj0iWTAiKSkgKyB5bGFiKCJZIikgKyB4bGFiKCJYMSIpDQpnMyA9IGRhdGEuZnJhbWUoeCA9IGMoLXBpLCBwaSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPXRhdSxzaXplPTEpICsgeWxhYihleHByZXNzaW9uKHRhdSkpICsgeGxhYigiWDEiKQ0KZzEgLyBnMiAvIGczDQpgYGANCg0KPGJyPiANCg0KIyMgSGFuZC1jb2RlZCBBSVBXIHcvbyBjcm9zcy1maXR0aW5nDQoNCldlIGRyYXcgYSBzYW1wbGUgb2YgJE49MjAwJCBhbmQgZXN0aW1hdGUgdGhlIG51aXNhbmNlIHBhcmFtZXRlcnMgJGUoWCk9RVtXfFhdJCwgJG0oMCxYKT1FW1l8Vz0wLFhdJCBhbmQgJG0oMSxYKT1FW1l8Vz0xLFhdJCB1c2luZyByYW5kb20gZm9yZXN0IHdpdGhvdXQgaG9uZXN0eSAoc2FtcGxlIHNpemUgdG9vIHNtYWxsIGZvciBob25lc3R5KSBhbmQgcGx1ZyB0aGUgcHJlZGljdGlvbnMgaW50byB0aGUgcHNldWRvIG91dGNvbWU6DQokJFx0aWxkZXtZfV97QVRFfSA9IFx1bmRlcmJyYWNle1xoYXR7bX0oMSxYKSAtIFxoYXR7bX0oMCxYKX1fe1x0ZXh0e291dGNvbWUgcHJlZGljdGlvbnN9fSArIFx1bmRlcmJyYWNle1xmcmFje1cgKFkgLSBcaGF0e219KDEsWCkpfXtcaGF0e2V9KFgpfSAtIFxmcmFjeygxLVcpIChZIC0gXGhhdHttfSgwLFgpKX17MS1caGF0e2V9KFgpfX1fe1x0ZXh0e3dlaWdodGVkIHJlc2lkdWFsc319JCQNCg0KYGBge3J9DQojIE5vIGNyb3NzLWZpdHRpbmcNCiMgUHJlZGljdCBwcm9wZW5zaXR5IHNjb3JlDQpyZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgsdyxob25lc3R5PUYpDQplaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQojIE1vZGVsIGNvbnRyb2wgb3V0Y29tZSB1c2luZyBvbmx5IGNvbnRyb2wgYW5kIHByZWRpY3QgZm9yIGFsbA0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4W3c9PTAsXSx5W3c9PTBdLGhvbmVzdHk9RikNCm0waGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQojIE1vZGVsIGNvbnRyb2wgb3V0Y29tZSB1c2luZyBvbmx5IGNvbnRyb2wgYW5kIHByZWRpY3QgZm9yIGFsbA0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4W3c9PTEsXSx5W3c9PTFdLGhvbmVzdHk9RikNCm0xaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQojIEdlbmVyYXRlIHBzZXVkby1vdXRjb21lDQpwc2V1ZG9feSA9ICBtMWhhdCAtIG0waGF0ICsNCiAgICAgICAgICAgIHcqKHktbTFoYXQpIC8gZWhhdCAtICgxLXcpKih5LW0waGF0KSAvICgxLWVoYXQpDQpgYGANCg0KVGFrZSB0aGUgbWVhbiBvZiB0aGUgcHNldWRvLW91dGNvbWUgYW5kIHJ1biBhIHQtdGVzdA0KDQpgYGB7cn0NCm1lYW4ocHNldWRvX3kpDQp0LnRlc3QocHNldWRvX3kpDQpgYGANCg0Kb3IgcnVuIGp1c3QgYW4gT0xTIHJlZ3Jlc3Npb24gd2l0aCBvbmx5IGEgY29uc3RhbnQgZm9yIHBvaW50IGVzdGltYXRpb24gYW5kIGluZmVyZW5jZSBpbiBvbmUgc3RlcC4NCg0KYGBge3J9DQpzdW1tYXJ5KGxtKHBzZXVkb195fjEpKQ0KYGBgDQoNCg0KPGJyPg0KDQojIyBIYW5kLWNvZGVkIEFJUFcgd2l0aCAyLWZvbGQgY3Jvc3MtZml0dGluZw0KDQpUaGUgdGhlb3JldGljYWwgcmVzdWx0cyByZXF1aXJlIHRoYXQgd2UgcHJlZGljdCB0aGUgbnVpc2FuY2UgcGFyYW1ldGVycyBvdXQtb2Ytc2FtcGxlLiBUaGUgZWFzaWVzdCB3YXkgdG8gZG8gdGhpcyBpcyB0d28tZm9sZCBjcm9zcy1maXR0aW5nOg0KDQotIFNwbGl0IHRoZSBzYW1wbGUgaW4gdHdvIHJhbmRvbSBzdWJzYW1wbGVzLCBTMSBhbmQgUzINCg0KLSBGb3JtIHByZWRpY3Rpb24gbW9kZWxzIGluIFMxLCB1c2UgaXQgdG8gcHJlZGljdCBpbiBTMg0KDQotIEZvcm0gcHJlZGljdGlvbiBtb2RlbHMgaW4gUzIsIHVzZSBpdCB0byBwcmVkaWN0IGluIFMxDQoNCi0gUGx1ZyB0aGUgcHJlZGljdGlvbiBpbiB0aGUgcHNldWRvLW91dGNvbWUgYW5kIHByb2NlZWQgYXMgYWJvdmUNCg0KDQpgYGB7cn0NCiMgMi1mb2xkIGNyb3NzLWZpdHRpbmcNCm0waGF0ID0gbTFoYXQgPSBlaGF0ID0gcmVwKE5BLG4pDQojIERyYXcgcmFuZG9tIGluZGljZXMgZm9yIHNhbXBsZSAxDQppbmRleF9zMSA9IHNhbXBsZSgxOm4sbi8yKQ0KIyBDcmVhdGUgUzENCngxID0geFtpbmRleF9zMSxdDQp3MSA9IHdbaW5kZXhfczFdDQp5MSA9IHlbaW5kZXhfczFdDQojIENyZWF0ZSBzYW1wbGUgMiB3aXRoIHRob3NlIG5vdCBpbiBTMQ0KeDIgPSB4Wy1pbmRleF9zMSxdDQp3MiA9IHdbLWluZGV4X3MxXQ0KeTIgPSB5Wy1pbmRleF9zMV0NCiMgTW9kZWwgaW4gUzEsIHByZWRpY3QgaW4gUzINCnJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeDEsdzEsaG9uZXN0eT1GKQ0KZWhhdFstaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgyKSRwcmVkaWN0aW9ucw0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4MVt3MT09MCxdLHkxW3cxPT0wXSxob25lc3R5PUYpDQptMGhhdFstaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgyKSRwcmVkaWN0aW9ucw0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4MVt3MT09MSxdLHkxW3cxPT0xXSxob25lc3R5PUYpDQptMWhhdFstaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgyKSRwcmVkaWN0aW9ucw0KIyBNb2RlbCBpbiBTMiwgcHJlZGljdCBpbiBTMQ0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4Mix3Mixob25lc3R5PUYpDQplaGF0W2luZGV4X3MxXSA9IHByZWRpY3QocmYsbmV3ZGF0YT14MSkkcHJlZGljdGlvbnMNCnJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeDJbdzI9PTAsXSx5Mlt3Mj09MF0saG9uZXN0eT1GKQ0KbTBoYXRbaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgxKSRwcmVkaWN0aW9ucw0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4Mlt3Mj09MSxdLHkyW3cyPT0xXSxob25lc3R5PUYpDQptMWhhdFtpbmRleF9zMV0gPSBwcmVkaWN0KHJmLG5ld2RhdGE9eDEpJHByZWRpY3Rpb25zDQojIEdlbmVyYXRlIHBzZXVkby1vdXRjb21lIGFuZCB0YWtlIGFuZCB0ZXN0IG1lYW4NCnBzZXVkb195ID0gIG0xaGF0IC0gbTBoYXQgKw0KICB3Kih5LW0xaGF0KSAvIGVoYXQgLSAoMS13KSooeS1tMGhhdCkgLyAoMS1laGF0KQ0Kc3VtbWFyeShsbShwc2V1ZG9feSB+IDEpKQ0KYGBgDQoNCjxicj4NCg0KDQojIyBBSVBXIHdpdGggNS1mb2xkIGNyb3NzLWZpdHRpbmcNCg0KMi1mb2xkIGNyb3NzLWZpdHRpbmcgaXMgZWFzeSB0byBpbXBsZW1lbnQgYnV0IGVzcGVjaWFsbHkgaW4gc21hbGwgc2FtcGxlIHNpemVzIHVzaW5nIG9ubHkgNTAlIG9mIHRoZSBkYXRhIHRvIGVzdGltYXRlIHRoZSBudWlzYW5jZSBwYXJhbWV0ZXJzIG1pZ2h0IGxlYWQgdG8gdW5zdGFibGUgcHJlZGljdGlvbnMuDQoNClRodXMsIHdlIHVzZSB0aGUgYERNTF9haXB3YCBmdW5jdGlvbiBvZiB0aGUgYGNhdXNhbERNTGAgcGFja2FnZSB0byBydW4gNS1mb2xkIGNyb3NzLWZpdHRpbmcuIFRoaXMgcGFja2FnZSByZXF1aXJlcyB0byBjcmVhdGUgdGhlIG1ldGhvZHMgdGhhdCB3ZSB1c2UgYmVjYXVzZSBpdCBhbGxvd3MgZm9yIGVuc2VtYmxlIG1ldGhvZHMuIEZvciBub3csIHdlIGZvY3VzIG9uIHRoZSBob25lc3QgcmFuZG9tIGZvcmVzdC4NCg0KV2l0aCA1LWZvbGQgY3Jvc3MtZml0dGluZywgd2Ugc3BsaXQgdGhlIHNhbXBsZSBpbiA1IGZvbGRzIGFuZCB1c2UgNCBmb2xkcyAoODAlIG9mIHRoZSBkYXRhKSB0byBwcmVkaWN0IHRoZSBsZWZ0IG91dCBmb2xkICgyMCUgb2YgdGhlIGRhdGEpLiBXZSBpdGVyYXRlIHN1Y2ggdGhhdCBldmVyeSBmb2xkIGlzIGxlZnQgb3V0IG9uY2UuDQoNCg0KYGBge3J9DQojIDUtZm9sZCBjcm9zcy1maXR0aW5nIHdpdGggY2F1c2FsRE1MIHBhY2thZ2UNCiMgQ3JlYXRlIGxlYXJuZXINCmZvcmVzdCA9IGNyZWF0ZV9tZXRob2QoImZvcmVzdF9ncmYiLGFyZ3M9bGlzdChob25lc3R5PUYpKQ0KIyBSdW4gYW5kIA0KYWlwdyA9IERNTF9haXB3KHksdyx4LG1sX3c9bGlzdChmb3Jlc3QpLG1sX3k9bGlzdChmb3Jlc3QpLGNmPTUpDQpzdW1tYXJ5KGFpcHckQVBPKQ0KcGxvdChhaXB3JEFQTykNCnN1bW1hcnkoYWlwdyRBVEUpDQpgYGANCg0KV2Ugb2JzZXJ2ZSB0d28gdGhpbmdzOg0KDQotIFRoZSBlc3RpbWF0b3Igd2l0aCA1LWZvbGQgY3Jvc3MtZml0dGluZyBjb21lcyBjbG9zZXN0IHRvIHRoZSB0cnVlIHZhbHVlDQoNCi0gSG93ZXZlciwgd2l0aG91dCBjcm9zcy1maXR0aW5nIGlzIGFsc28gY2xvc2UsIGJ1dCB3aXRoIGEgbXVjaCBtdWNoIHNtYWxsZXIgc3RhbmRhcmQgZXJyb3IuDQoNCkxldCdzIHNlZSB3aGV0aGVyIHRoZSBmb3JtZXIgaXMgb25seSBieSBjaGFuY2Ugb3Igc3lzdGVtYXRpYywgYW5kIGVzcGVjaWFsbHkgd2hldGhlciB0aGUgbGF0dGVyIGlzIHRvbyBnb29kIHRvIGJlIHRydWUuDQoNCjxicj4NCg0KDQojIyBTaW11bGF0aW9uIHN0dWR5IGhvbW9nZW5lb3VzIGVmZmVjdCBzZXR0aW5nDQoNCldlIHJ1biBhIHNpbXVsYXRpb24gc3R1ZHkgZHJhd2luZyAkTT0xLDAwMCQgc2FtcGxlcyBmcm9tIHRoZSBER1AgZGVzY3JpYmVkIGFib3ZlIGFuZCBlc3RpbWF0ZSB0aGUgZWZmZWN0IHdpdGggdGhyZWUgZGlmZmVyZW50IGVzdGltYXRvcnM6DQoNCi0gUGFydGlhbGx5IGxpbmVhciBtb2RlbCBlc3RpbWF0ZWQgd2l0aCA1LWZvbGQgY3Jvc3MtZml0dGluZw0KDQotIEFJUFcgd2l0aG91dCBjcm9zcy1maXR0aW5nDQoNCi0gQUlQVyB3aXRoIDUtZm9sZCBjcm9zcy1maXR0aW5nDQoNCkFkZGl0aW9uYWxseSB0byBiaWFzLCB2YXJpYW5jZSBhbmQgTVNFLCB3ZSBhbHNvIGNoZWNrIHRoZSBxdWFsaXR5IG9mIHRoZSBzdGFuZGFyZCBlcnJvcnMgdmlhIHRoZSBjb3ZlcmFnZSByYXRlLiBUaGUgY292ZXJhZ2UgcmF0ZSBjaGVja3MgaG93IG9mdGVuIHRoZSB0cnVlIHZhbHVlIGlzIGluY2x1ZGVkIGluIHRoZSBjb25maWRlbmNlIGludGVydmFscyAoc2VlIFtyaW5nIHRvc3MgYW5hbG9neV0oaHR0cHM6Ly9tZWRpdW0uY29tL0BFcGlFbGxpZS9oYXZpbmctY29uZmlkZW5jZS1pbi1jb25maWRlbmNlLWludGVydmFscy04Zjg4MTcxMmQ4MzcpIGFzIGFuIGludHVpdGl2ZSByZWZyZXNoZXIpLiANCg0KV2Ugd291bGQgbGlrZSB0byBoYXZlIG5vbWluYWwgY292ZXJhZ2UsIGkuZS4gZm9yIGEgOTUlIGNvbmZpZGVuY2UgbGV2ZWwgaXQgc2hvdWxkIGhhcHBlbiBpbiA5NSUgb2YgdGhlIHJlcGxpY2F0aW9ucywgZm9yIGEgOTAlIGNvbmZpZGVuY2UgbGV2ZWwgaW4gOTAlIG9mIHRoZSByZXBsaWNhdGlvbnMsIC4uLg0KDQoNCmBgYHtyfQ0KIyBzZXQgbnVtYmVyIG9mIHJlcGxpY2F0aW9ucw0Kbl9yZXAgPSAxMDAwICMgRGVjcmVhc2UgZm9yIGZhc3RlciBjb21wdXRhdGlvbg0KIyBpbml0aWFsaXplIHN0b3JhZ2UgZm9yIHJlc3VsdHMNCmNvdmVyYWdlID0gcmVzdWx0cyA9IG1hdHJpeChOQSxuX3JlcCwzKQ0KY29sbmFtZXMoY292ZXJhZ2UpID0gY29sbmFtZXMocmVzdWx0cykgPSBjKCJQTCBjZjUiLCJBSVBXIG5vIiwiQUlQVyBjZjUiKQ0KDQojIHN0YXJ0IHRoZSBzaW11bGF0aW9uDQpmb3IgKGkgaW4gMTpuX3JlcCkgew0KICB4ID0gbWF0cml4KHJ1bmlmKG4qcCwtcGkscGkpLG5jb2w9cCkNCiAgdyA9IHJiaW5vbShuLDEsZSh4WywxXSkpDQogIHkgPSB3Km0xKHhbLDFdKSArICgxLXcpKm0wKHhbLDFdKSArIHJub3JtKG4sMCwxKQ0KICANCiAgIyBwYXJ0aWFsbHkgbGluZWFyIG1vZGVsDQogIHBsID0gRE1MX3BhcnRpYWxfbGluZWFyKHksdyx4LG1sX3c9bGlzdChmb3Jlc3QpLG1sX3k9bGlzdChmb3Jlc3QpLGNmPTUpDQogIHJlc3VsdHNbaSwxXSA9IHBsJHJlc3VsdFsxXQ0KICBjb3ZlcmFnZVtpLDFdID0gKHBsJHJlc3VsdFsxXSAtIDEuOTYqcGwkcmVzdWx0WzJdIDwgdGhldGEgJiBwbCRyZXN1bHRbMV0gKyAxLjk2KnBsJHJlc3VsdFsyXSA+IHRoZXRhKQ0KICANCiAgIyBObyBjcm9zcy1maXR0aW5nDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeCx3LGhvbmVzdHk9RikNCiAgZWhhdCA9IHByZWRpY3QocmYsbmV3ZGF0YT14KSRwcmVkaWN0aW9ucw0KICByZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHhbdz09MCxdLHlbdz09MF0saG9uZXN0eT1GKQ0KICBtMGhhdCA9IHByZWRpY3QocmYsbmV3ZGF0YT14KSRwcmVkaWN0aW9ucw0KICByZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHhbdz09MSxdLHlbdz09MV0saG9uZXN0eT1GKQ0KICBtMWhhdCA9IHByZWRpY3QocmYsbmV3ZGF0YT14KSRwcmVkaWN0aW9ucw0KICBwc2V1ZG9feSA9ICBtMWhhdCAtIG0waGF0ICsNCiAgICB3Kih5LW0xaGF0KSAvIGVoYXQgLSAoMS13KSooeS1tMGhhdCkgLyAoMS1laGF0KQ0KICByZXN1bHRzW2ksMl0gPSBtZWFuKHBzZXVkb195KQ0KICB0dCA9IHQudGVzdChwc2V1ZG9feSkNCiAgY292ZXJhZ2VbaSwyXSA9ICh0dCRjb25mLmludFsxXSAgPCB0aGV0YSAmIHR0JGNvbmYuaW50WzJdID4gdGhldGEpDQoNCiAgIyA1LWZvbGQgY3Jvc3MtZml0dGluZyB3aXRoIGNhdXNhbERNTCBwYWNrYWdlIHJldXNpbmcgdGhlIGZvbGRzIGFuZCBwc2NvcmVzIG9mIFBMDQogIGFpcHcgPSBETUxfYWlwdyh5LHcseCxtbF95PWxpc3QoZm9yZXN0KSxjZj01LA0KICAgICAgICAgICAgICAgICAgZV9tYXQgPSBjYmluZCgxLXBsJGVfaGF0LHBsJGVfaGF0KSxjZl9tYXQgPSBwbCRjZl9tYXQpDQogIHJlc3VsdHNbaSwzXSA9IGFpcHckQVRFJHJlc3VsdHNbMV0NCiAgY292ZXJhZ2VbaSwzXSA9IChhaXB3JEFURSRyZXN1bHRzWzFdIC0gMS45NiphaXB3JEFURSRyZXN1bHRzWzJdIDwgdGhldGEgJiBhaXB3JEFURSRyZXN1bHRzWzFdICsgMS45NiphaXB3JEFURSRyZXN1bHRzWzJdID4gdGhldGEpDQp9DQpgYGANCg0KV2UgcGxvdCB0aGUgZXN0aW1hdG9yIGRpc3RyaWJ1dGlvbnMgYW5kIG5vdGUgdGhhdCB0aGUgZXN0aW1hdG9yIHdpdGhvdXQgY3Jvc3MtZml0dGluZyBzZWVtcyB0byBiZSBiaWFzZWQ6DQoNCg0KYGBge3J9DQphcy5kYXRhLmZyYW1lKHJlc3VsdHMpICU+JSBwaXZvdF9sb25nZXIoY29scz1ldmVyeXRoaW5nKCksbmFtZXNfdG8gPSAiRXN0aW1hdG9yIix2YWx1ZXNfdG8gPSAiY29lZiIpICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSBjb2VmLCBmaWxsID0gRXN0aW1hdG9yKSkgKyBnZW9tX2RlbnNpdHkoYWxwaGE9MC41KSArIHRoZW1lX2J3KCkgKyBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQ9dGhldGEpDQpgYGANCg0KVGhpcyBpcyBjb25maXJtZWQgYnkgdGhlIGRlY29tcG9zaXRpb24gb2YgdGhlIE1TRSAoc2VlIGZvcm11bGEgaW4gW1NOQl9QYXJ0aWFsbHlfbGluZWFyXShodHRwczovL21ja25hdXMuZ2l0aHViLmlvL2Fzc2V0cy9ub3RlYm9va3MvU05CL1NOQl9QYXJ0aWFsbHlfbGluZWFyLm5iLmh0bWwpIG5vdGVib29rKToNCg0KYGBge3J9DQpkYXRhLmZyYW1lKG1ldGhvZCA9IGNvbG5hbWVzKHJlc3VsdHMpLA0KICAgICAgICAgICBiaWFzMiA9IGNvbE1lYW5zKHJlc3VsdHMtdGhldGEpXjIsDQogICAgICAgICAgIHZhciA9IGNvbE1lYW5zKHN3ZWVwKHJlc3VsdHMsMixjb2xNZWFucyhyZXN1bHRzKSleMikpICU+JSANCiAgcGl2b3RfbG9uZ2VyKC1tZXRob2QsbmFtZXNfdG8gPSAiQ29tcG9uZW50Iix2YWx1ZXNfdG8gPSAiTVNFIikgJT4lDQogIGdncGxvdChhZXMoZmlsbD1mYWN0b3IoQ29tcG9uZW50LGxldmVscz1jKCJ2YXIiLCJiaWFzMiIpKSwgeT1NU0UsIHg9bWV0aG9kKSkgKyANCiAgZ2VvbV9iYXIocG9zaXRpb249InN0YWNrIiwgc3RhdD0iaWRlbnRpdHkiKSArIHNjYWxlX2ZpbGxfZGlzY3JldGUobmFtZSA9ICJDb21wb25lbnQiKQ0KYGBgDQoNCk5vdGFibHkgdGhlIHZhcmlhbmNlIG9mIHRoZSBwYXJ0aWFsbHkgbGluZWFyIGVzdGltYXRvciBpcyBzbWFsbGVyIGNvbXBhcmVkIHRvIGNyb3NzLWZpdHRlZCBBSVBXLCB3aGlsZSBib3RoIGFyZSBiYXNpY2FsbHkgdW5iaWFzZWQuIFRoaXMgbWFrZXMgc2Vuc2UgYmVjYXVzZSB3ZSBsb29rZWQgYXQgdGhlIGNhc2Ugd2l0aCBhY3R1YWwgZWZmZWN0IGhvbW9nZW5laXR5LCB3aGVyZSB0aGUgcGFydGlhbGx5IGxpbmVhciBlc3RpbWF0b3IgaXMgYW4gZWZmaWNpZW50IGVzdGltYXRvciBpbiBjYXNlIG9mIGhvbW9zY2VkYXN0aWMgZXJyb3JzLCB3aGljaCB3ZSBpbXBvc2UuDQoNCkZpbmFsbHksIGxldCdzIGNoZWNrIHRoZSBjb3ZlcmFnZSByYXRlOg0KDQpgYGB7cn0NCmRhdGEuZnJhbWUobWV0aG9kID0gY29sbmFtZXMocmVzdWx0cyksDQogICAgICAgICAgIGNvdmVyYWdlID0gY29sTWVhbnMoY292ZXJhZ2UpKSAlPiUgDQogIGdncGxvdChhZXMoeT1jb3ZlcmFnZSwgeD1tZXRob2QpKSArIGdlb21faGxpbmUoeWludGVyY2VwdD0wLjk1LGxpbmV0eXBlPSJkYXNoZWQiKSArIA0KICBnZW9tX3BvaW50KHNpemU9NSxzaGFwZT00KSArIHNjYWxlX2ZpbGxfZGlzY3JldGUobmFtZSA9ICJDb21wb25lbnQiKSArIHlsaW0oYygwLDEpKSArDQogIGdlb21faGxpbmUoeWludGVyY2VwdD1jKDAsMSkpDQpgYGANCg0KV2l0aG91dCBjcm9zcy1maXR0aW5nLCB0aGUgY292ZXJhZ2UgcmF0ZSBvZiBBSVBXIGlzIG9ubHkgNTAlLCB3aGljaCByZWZsZWN0cyB0aGUgYmlhcyBhbmQgdGhhdCB0aGUgZXN0aW1hdGVkIHN0YW5kYXJkIGVycm9ycyBhcmUgdG9vIHNtYWxsLiBUaGUgb3RoZXIgdHdvIHNsaWdodGx5IHVuZGVyY292ZXIsIGJ1dCBlc3BlY2lhbGx5IGNyb3NzLWZpdHRlZCBBSVBXIHdvcmtzIHdlbGwgaW4gdGVybXMgb2YgaW5mZXJlbmNlLg0KDQoNCjxicj4NCjxicj4NCg0KDQoNCiMgRWZmZWN0IGhldGVyb2dlbmVpdHkgd2l0aCBiYWxhbmNlZCB0cmVhdG1lbnQgc2hhcmVzDQoNCiMjIERHUA0KDQpOb3cgd2UgaW50cm9kdWNlIGhldGVyb2dlbmVvdXMgdHJlYXRtZW50IGVmZmVjdHMgbGVhdmluZyB0aGUgcmVzdCB1bmNoYW5nZWQ6DQoNCi0gJHA9MTAkIGluZGVwZW5kZW50IGNvdmFyaWF0ZXMgJFhfMSwuLi4sWF9rLC4uLixYX3sxMH0kIGRyYXduIGZyb20gYSB1bmlmb3JtIGRpc3RyaWJ1dGlvbjogJFhfayBcc2ltIHVuaWZvcm0oLVxwaSxccGkpJA0KDQotIFRoZSB0cmVhdG1lbnQgbW9kZWwgaXMgJFcgXHNpbSBCZXJub3VsbGkoXHVuZGVyYnJhY2V7XFBoaShzaW4oWF8xKSl9X3tlKFgpfSkkLCB3aGVyZSAkXFBoaShcY2RvdCkkIGlzIHRoZSBzdGFuZGFyZCBub3JtYWwgY3VtdWxhdGl2ZSBkZW5zaXR5IGZ1bmN0aW9uDQoNCi0gVGhlIG91dGNvbWUgbW9kZWwgb2YgdGhlIHRyZWF0ZWQgaXMgJFkoMSkgPSBcdW5kZXJicmFjZXtzaW4oWF8xKX1fe21fMShYKX0rIFx2YXJlcHNpbG9uJCwgd2l0aCAkXHZhcmVwc2lsb24gXHNpbSBOKDAsMSkkDQoNCi0gVGhlIG91dGNvbWUgbW9kZWwgb2YgdGhlIGNvbnRyb2xzIGlzICRZKDApID0gXHVuZGVyYnJhY2V7Y29zKFhfMSsxLzJccGkpfV97bV8wKFgpfSsgXHZhcmVwc2lsb24kLCB3aXRoICRcdmFyZXBzaWxvbiBcc2ltIE4oMCwxKSQNCg0KVGhpcyBtZWFucyB0aGF0IHRoZSBBVEUgaXMgZXF1YWwgdG8gemVybyAoJFx0YXVfe0FURX09MCQpIGJ1dCB3ZSBoYXZlIHRyZW1lbmRvdXMgZWZmZWN0IGhldGVyb2dlbmVpdHk6IA0KDQoNCmBgYHtyfQ0KeCA9IG1hdHJpeChydW5pZihuKnAsLXBpLHBpKSxuY29sPXApDQplID0gZnVuY3Rpb24oeCl7cG5vcm0oc2luKHgpKX0NCm0xID0gZnVuY3Rpb24oeCl7c2luKHgpfQ0KbTAgPSBmdW5jdGlvbih4KXtjb3MoeCsxLzIqcGkpfQ0KdGF1ID0gZnVuY3Rpb24oeCl7bTEoeCkgLSBtMCh4KX0NCncgPSByYmlub20obiwxLGUoeFssMV0pKQ0KeSA9IHcqbTEoeFssMV0pICsgKDEtdykqbTAoeFssMV0pICsgcm5vcm0obiwwLDEpDQoNCmcxID0gZGF0YS5mcmFtZSh4ID0gYygtcGksIHBpKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49ZSxzaXplPTEpICsgeWxhYigiZSIpICsgeGxhYigiWDEiKQ0KZzIgPSBkYXRhLmZyYW1lKHggPSBjKC1waSwgcGkpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1tMSxzaXplPTEsYWVzKGNvbG91cj0iWTEiKSkgKyANCiAgc3RhdF9mdW5jdGlvbihmdW49bTAsc2l6ZT0xLGFlcyhjb2xvdXI9IlkwIikpICsgeWxhYigiWSIpICsgeGxhYigiWDEiKQ0KZzMgPSBkYXRhLmZyYW1lKHggPSBjKC1waSwgcGkpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj10YXUsc2l6ZT0xKSArIHlsYWIoZXhwcmVzc2lvbih0YXUpKSArIHhsYWIoIlgxIikNCmcxIC8gZzIgLyBnMw0KYGBgDQoNCjxicj4NCg0KDQojIyBTaW11bGF0aW9uIHN0dWR5IGhldGVyb2dlbmVvdXMgZWZmZWN0IHNldHRpbmcNCg0KV2UgcnVuIGEgc2ltdWxhdGlvbiBzdHVkeSBkcmF3aW5nICRNPTEsMDAwJCBzYW1wbGVzIGZyb20gdGhlIERHUCBkZXNjcmliZWQgYWJvdmUgYW5kIGVzdGltYXRlIHRoZSBlZmZlY3Qgd2l0aCB0aHJlZSBkaWZmZXJlbnQgZXN0aW1hdG9yczoNCg0KLSBQYXJ0aWFsbHkgbGluZWFyIG1vZGVsIGVzdGltYXRlZCB3aXRoIDUtZm9sZCBjcm9zcy1maXR0aW5nDQoNCi0gQUlQVyB3aXRob3V0IGNyb3NzLWZpdHRpbmcNCg0KLSBBSVBXIHdpdGggNS1mb2xkIGNyb3NzLWZpdHRpbmcNCg0KDQpgYGB7cn0NCiMgaW5pdGlhbGl6ZSBzdG9yYWdlIGZvciByZXN1bHRzDQpjb3ZlcmFnZV9oZXQgPSByZXN1bHRzX2hldCA9IG1hdHJpeChOQSxuX3JlcCwzKQ0KY29sbmFtZXMoY292ZXJhZ2VfaGV0KSA9IGNvbG5hbWVzKHJlc3VsdHNfaGV0KSA9IGMoIlBMIGNmNSIsIkFJUFcgbm8iLCJBSVBXIGNmNSIpDQoNCiMgc3RhcnQgdGhlIHNpbXVsYXRpb24NCmZvciAoaSBpbiAxOm5fcmVwKSB7DQogIHggPSBtYXRyaXgocnVuaWYobipwLC1waSxwaSksbmNvbD1wKQ0KICB3ID0gcmJpbm9tKG4sMSxlKHhbLDFdKSkNCiAgeSA9IHcqbTEoeFssMV0pICsgKDEtdykqbTAoeFssMV0pICsgcm5vcm0obiwwLDEpDQogIA0KICAjIHBhcnRpYWxseSBsaW5lYXIgbW9kZWwNCiAgcGwgPSBETUxfcGFydGlhbF9saW5lYXIoeSx3LHgsbWxfdz1saXN0KGZvcmVzdCksbWxfeT1saXN0KGZvcmVzdCksY2Y9NSkNCiAgcmVzdWx0c19oZXRbaSwxXSA9IHBsJHJlc3VsdFsxXQ0KICBjb3ZlcmFnZV9oZXRbaSwxXSA9IChwbCRyZXN1bHRbMV0gLSAxLjk2KnBsJHJlc3VsdFsyXSA8IDAgJiBwbCRyZXN1bHRbMV0gKyAxLjk2KnBsJHJlc3VsdFsyXSA+IDApDQogIA0KICAjIE5vIGNyb3NzLWZpdHRpbmcNCiAgcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4LHcsaG9uZXN0eT1GKQ0KICBlaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeFt3PT0wLF0seVt3PT0wXSxob25lc3R5PUYpDQogIG0waGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeFt3PT0xLF0seVt3PT0xXSxob25lc3R5PUYpDQogIG0xaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHBzZXVkb195ID0gIG0xaGF0IC0gbTBoYXQgKw0KICAgIHcqKHktbTFoYXQpIC8gZWhhdCAtICgxLXcpKih5LW0waGF0KSAvICgxLWVoYXQpDQogIHJlc3VsdHNfaGV0W2ksMl0gPSBtZWFuKHBzZXVkb195KQ0KICB0dCA9IHQudGVzdChwc2V1ZG9feSkNCiAgY292ZXJhZ2VfaGV0W2ksMl0gPSAodHQkY29uZi5pbnRbMV0gIDwgMCAmIHR0JGNvbmYuaW50WzJdID4gMCkNCiAgDQogIGFpcHcgPSBETUxfYWlwdyh5LHcseCxtbF95PWxpc3QoZm9yZXN0KSxjZj01LA0KICAgICAgICAgICAgICAgICAgZV9tYXQgPSBjYmluZCgxLXBsJGVfaGF0LHBsJGVfaGF0KSxjZl9tYXQgPSBwbCRjZl9tYXQpDQogIHJlc3VsdHNfaGV0W2ksM10gPSBhaXB3JEFURSRyZXN1bHRzWzFdDQogIGNvdmVyYWdlX2hldFtpLDNdID0gKGFpcHckQVRFJHJlc3VsdHNbMV0gLSAxLjk2KmFpcHckQVRFJHJlc3VsdHNbMl0gPCAwICYgYWlwdyRBVEUkcmVzdWx0c1sxXSArIDEuOTYqYWlwdyRBVEUkcmVzdWx0c1syXSA+IDApDQp9DQpgYGANCg0KV2UgcGxvdCB0aGUgZXN0aW1hdG9yIGRpc3RyaWJ1dGlvbnMgYW5kIG5vdGUgdGhhdCBiYXNpY2FsbHkgYWxsIGVzdGltYXRvcnMgYXJlIHVuYmlhc2VkOg0KDQoNCmBgYHtyfQ0KYXMuZGF0YS5mcmFtZShyZXN1bHRzX2hldCkgJT4lIHBpdm90X2xvbmdlcihjb2xzPWV2ZXJ5dGhpbmcoKSxuYW1lc190byA9ICJFc3RpbWF0b3IiLHZhbHVlc190byA9ICJjb2VmIikgJT4lDQogIGdncGxvdChhZXMoeCA9IGNvZWYsIGZpbGwgPSBFc3RpbWF0b3IpKSArIGdlb21fZGVuc2l0eShhbHBoYT0wLjUpICsgdGhlbWVfYncoKSArIGdlb21fdmxpbmUoeGludGVyY2VwdD0wKQ0KYGBgDQoNClRoaXMgaXMgY29uZmlybWVkIGJ5IHRoZSBkZWNvbXBvc2l0aW9uIG9mIHRoZSBNU0U6DQoNCmBgYHtyfQ0KZGF0YS5mcmFtZShtZXRob2QgPSBjb2xuYW1lcyhyZXN1bHRzX2hldCksDQogICAgICAgICAgIGJpYXMyID0gY29sTWVhbnMocmVzdWx0c19oZXQtMCleMiwNCiAgICAgICAgICAgdmFyID0gY29sTWVhbnMoc3dlZXAocmVzdWx0c19oZXQsMixjb2xNZWFucyhyZXN1bHRzX2hldCkpXjIpKSAlPiUgDQogIHBpdm90X2xvbmdlcigtbWV0aG9kLG5hbWVzX3RvID0gIkNvbXBvbmVudCIsdmFsdWVzX3RvID0gIk1TRSIpICU+JQ0KICBnZ3Bsb3QoYWVzKGZpbGw9ZmFjdG9yKENvbXBvbmVudCxsZXZlbHM9YygidmFyIiwiYmlhczIiKSksIHk9TVNFLCB4PW1ldGhvZCkpICsgDQogIGdlb21fYmFyKHBvc2l0aW9uPSJzdGFjayIsIHN0YXQ9ImlkZW50aXR5IikgKyBzY2FsZV9maWxsX2Rpc2NyZXRlKG5hbWUgPSAiQ29tcG9uZW50IikNCmBgYA0KDQpOb3RhYmx5IHRoZSBwYXJ0aWFsbHkgbGluZWFyIGVzdGltYXRvciBpcyB1bmJpYXNlZCBhbHRob3VnaCBpdCBhc3N1bWVzIGVmZmVjdCBoZXRlcm9nZW5laXR5LiBIb3dldmVyLCBpdCBzaG93cyBhIGhpZ2hlciB2YXJpYW5jZSB0aGFuIHRoZSBBSVBXIGVzdGltYXRvci4gVGhpcyBpcyBub3QgdW5leHBlY3RlZCBiZWNhdXNlIEFJUFcgaXMgYW4gZWZmaWNpZW50IGVzdGltYXRvciBpbiB0aGUgaGV0ZXJvZ2VuZW91cyBlZmZlY3RzIHNldHRpbmcuIEJ1dCBjcm9zcy1maXR0aW5nIHNlZW1zIHRvIGJlIGhhcm1mdWwgYXMgd2UgaGF2ZSBubyBiaWFzIGFuZCBsb3dlciB2YXJpYW5jZSB3aXRob3V0IGFsbCB0aGlzIGFkZGl0aW9uYWwgZWZmb3J0Lg0KDQpCVVQsIGxldCdzIGNoZWNrIHRoZSBjb3ZlcmFnZSByYXRlOg0KDQpgYGB7cn0NCmRhdGEuZnJhbWUobWV0aG9kID0gY29sbmFtZXMocmVzdWx0c19oZXQpLA0KICAgICAgICAgICBjb3ZlcmFnZSA9IGNvbE1lYW5zKGNvdmVyYWdlX2hldCkpICU+JSANCiAgZ2dwbG90KGFlcyh5PWNvdmVyYWdlLCB4PW1ldGhvZCkpICsgZ2VvbV9obGluZSh5aW50ZXJjZXB0PTAuOTUsbGluZXR5cGU9ImRhc2hlZCIpICsgDQogIGdlb21fcG9pbnQoc2l6ZT01LHNoYXBlPTQpICsgc2NhbGVfZmlsbF9kaXNjcmV0ZShuYW1lID0gIkNvbXBvbmVudCIpICsgeWxpbShjKDAsMSkpICsNCiAgZ2VvbV9obGluZSh5aW50ZXJjZXB0PWMoMCwxKSkNCmBgYA0KDQpDcm9zcy1maXR0ZWQgQUlQVyBzaG93cyBuZWFybHkgcGVyZmVjdCBjb3ZlcmFnZSwgd2hpbGUgdGhlIHN0YW5kYXJkIGVycm9ycyB3aXRob3V0IGNyb3NzLWZpdHRpbmcgYXJlIG11Y2ggdG9vIHNtYWxsLg0KDQokXFJpZ2h0YXJyb3ckIENyb3NzLWZpdHRpbmcgaXMgbm90IG5lY2Vzc2FyaWx5IHJlcXVpcmVkIHRvIHJlbW92ZSBiaWFzIGluIHRoZSBwb2ludCBlc3RpbWF0ZXMgZHVlIHRvIG92ZXJmaXR0aW5nLCBidXQgdG8gcmVtb3ZlIGRvd253YXJkIGJpYXMgaW4gdGhlIHN0YW5kYXJkIGVycm9ycy4gVGhlIHRydWUgQVRFIGlzIHplcm8gaW4gb3VyIGNhc2UsIGJ1dCB3ZSB3b3VsZCBmaW5kIHNpZ25pZmljYW50IGVmZmVjdHMgaW4gYWJvdXQgMjAlIG9mIHRoZSBjYXNlcyBpbnN0ZWFkIG9mIHRoZSA1JSB0aGF0IHdlIGFsbG93IHRvIGhhcHBlbiBnaXZlbiBvdXIgY29uZmlkZW5jZSBsZXZlbC4gDQoNCjxicj4NCjxicj4NCg0KDQoNCiMgRWZmZWN0IGhldGVyb2dlbmVpdHkgd2l0aCB1bmJhbGFuY2VkIHRyZWF0bWVudCBzaGFyZXMNCg0KIyMgREdQDQoNCk5vdyB3ZSBpbnRyb2R1Y2UgdW5iYWxhbmNlZCB0cmVhdG1lbnQgc2hhcmVzIGxlYXZpbmcgdGhlIHJlc3QgdW5jaGFuZ2VkOg0KDQotICRwPTEwJCBpbmRlcGVuZGVudCBjb3ZhcmlhdGVzICRYXzEsLi4uLFhfaywuLi4sWF97MTB9JCBkcmF3biBmcm9tIGEgdW5pZm9ybSBkaXN0cmlidXRpb246ICRYX2sgXHNpbSB1bmlmb3JtKC1ccGksXHBpKSQNCg0KLSBUaGUgdHJlYXRtZW50IG1vZGVsIGlzICRXIFxzaW0gQmVybm91bGxpKFx1bmRlcmJyYWNle1xQaGkoc2luKFhfMS0wLjUpKX1fe2UoWCl9KSQsIHdoZXJlICRcUGhpKFxjZG90KSQgaXMgdGhlIHN0YW5kYXJkIG5vcm1hbCBjdW11bGF0aXZlIGRlbnNpdHkgZnVuY3Rpb24NCg0KLSBUaGUgb3V0Y29tZSBtb2RlbCBvZiB0aGUgdHJlYXRlZCBpcyAkWSgxKSA9IFx1bmRlcmJyYWNle3NpbihYXzEpfV97bV8xKFgpfSsgXHZhcmVwc2lsb24kLCB3aXRoICRcdmFyZXBzaWxvbiBcc2ltIE4oMCwxKSQNCg0KLSBUaGUgb3V0Y29tZSBtb2RlbCBvZiB0aGUgY29udHJvbHMgaXMgJFkoMCkgPSBcdW5kZXJicmFjZXtjb3MoWF8xKzEvMlxwaSl9X3ttXzAoWCl9KyBcdmFyZXBzaWxvbiQsIHdpdGggJFx2YXJlcHNpbG9uIFxzaW0gTigwLDEpJA0KDQpXZSBub3cgZXhwZWN0IHJvdWdobHkgMS8zIHRyZWF0ZWQgYW5kIGluY3JlYXNlIHRoZSBzYW1wbGUgc2l6ZSB0byAzMDAgc3VjaCB0aGF0IGF0IGxlYXN0IDEwMCBvYnNlcnZhdGlvbnMgYXJlIGluIGVhY2ggdHJlYXRtZW50IGFybToNCg0KDQpgYGB7cn0NCm4gPSAzMDANCg0KeCA9IG1hdHJpeChydW5pZihuKnAsLXBpLHBpKSxuY29sPXApDQplID0gZnVuY3Rpb24oeCl7cG5vcm0oc2luKHgpLTAuNSl9DQptMSA9IGZ1bmN0aW9uKHgpe3Npbih4KX0NCm0wID0gZnVuY3Rpb24oeCl7Y29zKHgrMS8yKnBpKX0NCnRhdSA9IGZ1bmN0aW9uKHgpe20xKHgpIC0gbTAoeCl9DQp3ID0gcmJpbm9tKG4sMSxlKHhbLDFdKSkNCnkgPSB3Km0xKHhbLDFdKSArICgxLXcpKm0wKHhbLDFdKSArIHJub3JtKG4sMCwxKQ0KDQpnMSA9IGRhdGEuZnJhbWUoeCA9IGMoLXBpLCBwaSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPWUsc2l6ZT0xKSArIHlsYWIoImUiKSArIHhsYWIoIlgxIikNCmcyID0gZGF0YS5mcmFtZSh4ID0gYygtcGksIHBpKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49bTEsc2l6ZT0xLGFlcyhjb2xvdXI9IlkxIikpICsgDQogIHN0YXRfZnVuY3Rpb24oZnVuPW0wLHNpemU9MSxhZXMoY29sb3VyPSJZMCIpKSArIHlsYWIoIlkiKSArIHhsYWIoIlgxIikNCmczID0gZGF0YS5mcmFtZSh4ID0gYygtcGksIHBpKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49dGF1LHNpemU9MSkgKyB5bGFiKGV4cHJlc3Npb24odGF1KSkgKyB4bGFiKCJYMSIpDQpnMSAvIGcyIC8gZzMNCmBgYA0KDQo8YnI+DQoNCg0KIyMjIFNpbXVsYXRpb24gc3R1ZHkgdW5iYWxhbmNlZCB0cmVhdG1lbnQgc2hhcmVzDQoNCldlIHJ1biBhIHNpbXVsYXRpb24gc3R1ZHkgZHJhd2luZyAkTT0xLDAwMCQgc2FtcGxlcyBmcm9tIHRoZSBER1AgZGVzY3JpYmVkIGFib3ZlIGFuZCBlc3RpbWF0ZSB0aGUgZWZmZWN0IHdpdGggdGhyZWUgZGlmZmVyZW50IGVzdGltYXRvcnM6DQoNCi0gUGFydGlhbGx5IGxpbmVhciBtb2RlbCBlc3RpbWF0ZWQgd2l0aCA1LWZvbGQgY3Jvc3MtZml0dGluZw0KDQotIEFJUFcgd2l0aG91dCBjcm9zcy1maXR0aW5nDQoNCi0gQUlQVyB3aXRoIDUtZm9sZCBjcm9zcy1maXR0aW5nDQoNCg0KYGBge3J9DQojIGluaXRpYWxpemUgc3RvcmFnZSBmb3IgcmVzdWx0cw0KY292ZXJhZ2VfdW5iYWwgPSByZXN1bHRzX3VuYmFsID0gbWF0cml4KE5BLG5fcmVwLDMpDQpjb2xuYW1lcyhjb3ZlcmFnZV91bmJhbCkgPSBjb2xuYW1lcyhyZXN1bHRzX3VuYmFsKSA9IGMoIlBMIGNmNSIsIkFJUFcgbm8iLCJBSVBXIGNmNSIpDQoNCiMgc3RhcnQgc2ltdWxhdGlvbg0KZm9yIChpIGluIDE6bl9yZXApIHsNCiAgeCA9IG1hdHJpeChydW5pZihuKnAsLXBpLHBpKSxuY29sPXApDQogIHcgPSByYmlub20obiwxLGUoeFssMV0pKQ0KICB5ID0gdyptMSh4WywxXSkgKyAoMS13KSptMCh4WywxXSkgKyBybm9ybShuLDAsMSkNCiAgDQogICMgcGFydGlhbGx5IGxpbmVhciBtb2RlbA0KICBwbCA9IERNTF9wYXJ0aWFsX2xpbmVhcih5LHcseCxtbF93PWxpc3QoZm9yZXN0KSxtbF95PWxpc3QoZm9yZXN0KSxjZj01KQ0KICByZXN1bHRzX3VuYmFsW2ksMV0gPSBwbCRyZXN1bHRbMV0NCiAgY292ZXJhZ2VfdW5iYWxbaSwxXSA9IChwbCRyZXN1bHRbMV0gLSAxLjk2KnBsJHJlc3VsdFsyXSA8IDAgJiBwbCRyZXN1bHRbMV0gKyAxLjk2KnBsJHJlc3VsdFsyXSA+IDApDQogIA0KICAjIE5vIGNyb3NzLWZpdHRpbmcNCiAgcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4LHcsaG9uZXN0eT1GKQ0KICBlaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeFt3PT0wLF0seVt3PT0wXSxob25lc3R5PUYpDQogIG0waGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeFt3PT0xLF0seVt3PT0xXSxob25lc3R5PUYpDQogIG0xaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHBzZXVkb195ID0gIG0xaGF0IC0gbTBoYXQgKw0KICAgIHcqKHktbTFoYXQpIC8gZWhhdCAtICgxLXcpKih5LW0waGF0KSAvICgxLWVoYXQpDQogIHJlc3VsdHNfdW5iYWxbaSwyXSA9IG1lYW4ocHNldWRvX3kpDQogIHR0ID0gdC50ZXN0KHBzZXVkb195KQ0KICBjb3ZlcmFnZV91bmJhbFtpLDJdID0gKHR0JGNvbmYuaW50WzFdICA8IDAgJiB0dCRjb25mLmludFsyXSA+IDApDQogIA0KICAjIDUtZm9sZCBjcm9zcy1maXR0aW5nIHdpdGggY2F1c2FsRE1MIHBhY2thZ2UgcmV1c2luZyB0aGUgZm9sZHMgYW5kIHBzY29yZXMgb2YgUEwNCiAgYWlwdyA9IERNTF9haXB3KHksdyx4LG1sX3k9bGlzdChmb3Jlc3QpLGNmPTUsDQogICAgICAgICAgICAgICAgICBlX21hdCA9IGNiaW5kKDEtcGwkZV9oYXQscGwkZV9oYXQpLGNmX21hdCA9IHBsJGNmX21hdCkNCiAgcmVzdWx0c191bmJhbFtpLDNdID0gYWlwdyRBVEUkcmVzdWx0c1sxXQ0KICBjb3ZlcmFnZV91bmJhbFtpLDNdID0gKGFpcHckQVRFJHJlc3VsdHNbMV0gLSAxLjk2KmFpcHckQVRFJHJlc3VsdHNbMl0gPCAwICYgYWlwdyRBVEUkcmVzdWx0c1sxXSArIDEuOTYqYWlwdyRBVEUkcmVzdWx0c1syXSA+IDApDQp9DQpgYGANCg0KV2UgcGxvdCB0aGUgZXN0aW1hdG9yIGRpc3RyaWJ1dGlvbnM6DQoNCmBgYHtyLCB3YXJuaW5nID0gRiwgbWVzc2FnZSA9IEZ9DQphcy5kYXRhLmZyYW1lKHJlc3VsdHNfdW5iYWwpICU+JSBwaXZvdF9sb25nZXIoY29scz1ldmVyeXRoaW5nKCksbmFtZXNfdG8gPSAiRXN0aW1hdG9yIix2YWx1ZXNfdG8gPSAiY29lZiIpICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSBjb2VmLCBmaWxsID0gRXN0aW1hdG9yKSkgKyBnZW9tX2RlbnNpdHkoYWxwaGE9MC41KSArIHRoZW1lX2J3KCkgKyBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQ9MCkNCmBgYA0KDQpCT09NISEhIE1heWJlIHlvdSB0aG91Z2h0IHRoYXQgdGhlIGVmZmVjdCBob21vZ2VuZWl0eSBhc3N1bXB0aW9uIGltcG9zZWQgYnkgdGhlIHBhcnRpYWxseSBsaW5lYXIgbW9kZWwgd2FzIGhhcm1sZXNzIGdpdmVuIHRoYXQgaXQgd29ya2VkIG5pY2VseSBhYm92ZSwgYnV0IHRoZSA1MC01MCB0cmVhdG1lbnQgc2hhcmUgaXMganVzdCBuaWNlIGluIHRoaXMgcmVnYXJkIChzZWUgW1PFgm9jennFhHNraSAoMjAyMCldKGh0dHBzOi8vZG9pLm9yZy8xMC4xMTYyL3Jlc3RfYV8wMDk1MykgZm9yIGEgbmljZSBkaXNjdXNzaW9uIGluIGNhc2Ugb2YgT0xTKS4gSW4gdGhlIHByZXNlbmNlIG9mIGhldGVyb2dlbmVvdXMgZWZmZWN0cywgZXN0aW1hdG9ycyBhc3N1bWluZyBlZmZlY3QgaG9tb2dlbmVpdHkgZXN0aW1hdGUgc29tZSBjYXVzYWwgZWZmZWN0LCBidXQgbm90IG5lY2Vzc2FyaWx5IHRoZSBBVEUuIFRoZSBlc3RpbWF0b3IgZGlzdHJpYnV0aW9uIGNlbnRlcnMgbmljZWx5IGFyb3VuZCAwLjUsIHdoaWxlIHdlIGtub3cgaXQgc2hvdWxkIGNlbnRlciBhcm91bmQgemVyby4NCg0KVGhpcyBpcyBjb25maXJtZWQgYnkgdGhlIGRlY29tcG9zaXRpb24gb2YgdGhlIE1TRSBzaG93aW5nIGEgaHVnZSBiaWFzOg0KYGBge3J9DQpkYXRhLmZyYW1lKG1ldGhvZCA9IGNvbG5hbWVzKHJlc3VsdHNfdW5iYWwpLA0KICAgICAgICAgICBiaWFzMiA9IGNvbE1lYW5zKHJlc3VsdHNfdW5iYWwtMCxuYS5ybT1UKV4yLA0KICAgICAgICAgICB2YXIgPSBjb2xNZWFucyhzd2VlcChyZXN1bHRzX3VuYmFsLDIsY29sTWVhbnMocmVzdWx0c191bmJhbCxuYS5ybT1UKSleMixuYS5ybT1UKSkgJT4lIA0KICBwaXZvdF9sb25nZXIoLW1ldGhvZCxuYW1lc190byA9ICJDb21wb25lbnQiLHZhbHVlc190byA9ICJNU0UiKSAlPiUNCiAgZ2dwbG90KGFlcyhmaWxsPWZhY3RvcihDb21wb25lbnQsbGV2ZWxzPWMoInZhciIsImJpYXMyIikpLCB5PU1TRSwgeD1tZXRob2QpKSArIA0KICBnZW9tX2Jhcihwb3NpdGlvbj0ic3RhY2siLCBzdGF0PSJpZGVudGl0eSIpICsgc2NhbGVfZmlsbF9kaXNjcmV0ZShuYW1lID0gIkNvbXBvbmVudCIpDQpgYGANCg0KVGhpcyBraWxscyBvZiBjb3Vyc2UgYWxzbyB0aGUgY292ZXJhZ2UgcmF0ZToNCg0KYGBge3J9DQpkYXRhLmZyYW1lKG1ldGhvZCA9IGNvbG5hbWVzKHJlc3VsdHNfdW5iYWwpLA0KICAgICAgICAgICBjb3ZlcmFnZSA9IGNvbE1lYW5zKGNvdmVyYWdlX3VuYmFsLG5hLnJtPVQpKSAlPiUgDQogIGdncGxvdChhZXMoeT1jb3ZlcmFnZSwgeD1tZXRob2QpKSArIGdlb21faGxpbmUoeWludGVyY2VwdD0wLjk1LGxpbmV0eXBlPSJkYXNoZWQiKSArIA0KICBnZW9tX3BvaW50KHNpemU9NSxzaGFwZT00KSArIHNjYWxlX2ZpbGxfZGlzY3JldGUobmFtZSA9ICJDb21wb25lbnQiKSArIHlsaW0oYygwLDEpKSArDQogIGdlb21faGxpbmUoeWludGVyY2VwdD1jKDAsMSkpDQpgYGANCg0KJFxSaWdodGFycm93JCBXZSB3b3VsZCByZWplY3QgdGhlIE51bGwgb2YgJFx0YXVfe0FURX09MCQsIHdoaWNoIGlzIHRydWUgaW4gb3VyIHNldHRpbmcsIGluIDgwJSBvZiB0aGUgY2FzZXMgaWYgd2UgaW1wb3NlZCB0aGUgYXNzdW1wdGlvbiBvZiBlZmZlY3QgaG9tb2dlbmVpdHkuDQoNCjxicj4NCjxicj4NCg0KDQoNCiMgVGFrZS1hd2F5DQogDQogLSBXZSBjYW4gcHJvZ3JhbSBhIGNyb3NzLWZpdCBEb3VibGUgTUwgQUlQVyBlc3RpbWF0b3Igd2l0aCBmZXcgbGluZXMgb2YgY29kZQ0KIA0KIC0gQ3Jvc3MtZml0dGluZyBtYWtlcyBhIGRpZmZlcmVuY2UsIGVzcGVjaWFsbHkgd2hlbiBpdCBjb21lcyB0byBpbmZlcmVuY2UNCiANCiAtIEVzdGltYXRvcnMgYXNzdW1pbmcgZWZmZWN0IGhvbW9nZW5laXR5IGNhbiBkcmFtYXRpY2FsbHkgYnJlYWsgZG93biBpbiB0aGUgcHJlc2VuY2Ugb2YgaGV0ZXJvZ2VuZWl0eQ0KIA0KPGJyPg0KPGJyPg0KIA0KIA0KIyBTdWdnZXN0aW9ucyB0byBwbGF5IHdpdGggdGhlIHRveSBtb2RlbA0KDQpUaGUgd2hvbGUgdGhpbmcgcmFuIHNldmVyYWwgaG91cnMgb24gbXkgbGFwdG9wLCBzbyB5b3Ugc2hvdWxkIGRlY3JlYXNlICpuX3JlcCogZm9yIHRoZSBmaXJzdCBwbGF5IGFuZCB0aGVuIHJ1biBpdCBvdmVyIG5pZ2h0IHdpdGggbW9yZS4NCg0KU29tZSBzdWdnZXN0aW9uczoNCiANCi0gTGV0IHRoZSB0cmVhdG1lbnQgc2hhcmVzIGdvIGUuZy4gZnJvbSAxMCUgdG8gOTAlIGluIDEwJSBzdGVwcyBhbmQgd2F0Y2ggaG93IHlvdSBjYW4gYmFzaWNhbGx5IGdldCBldmVyeSBlZmZlY3QgeW91IGxpa2Ugd2l0aCB0aGUgcGFydGlhbGx5IGxpbmVhciBtb2RlbA0KIA0KLSBNb2RpZnkgREdQIChpbmNyZWFzZSB0aGV0YSwgY29ycmVsYXRpb24gb2YgY292YXJpYXRlcywgY29lZmZpY2llbnRzLCBub2lzZSB0ZXJtLCAuLi4pDQoNCi0gSW5jcmVhc2UgdGhlIG51bWJlciBvZiBvYnNlcnZhdGlvbnMNCg0KLSBJbmNyZWFzZSBjcm9zcy1maXR0aW5nIGZvbGRzIHRvIDEwIGFuZC9vciAyMA0KDQog